Leetcode:60. 第K个排列
给出集合 [1,2,3,…,n]
,其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k,返回第 k 个排列。
说明:
- 给定 n 的范围是 [1, 9]。
- 给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3 输出: "213"
示例 2:
输入: n = 4, k = 9 输出: "2314"
解题思路:
递归,求余。观察过最快的代码,就是把阶乘先求出来了(1-9的阶乘)。
假设当前剩余的字符个数为n,那么选择任意一个数之后,接下来都有mod=(n-2)!的排列。当前选择第K个排列,于是num=k/mod; re=k%mod;那么num和re分别表示倍数和余数。
1.当余数re=0时,说明应该选择当前剩余的第num大的数,之后再把剩余的数逆序输出。
2. 当余数re!=0时,说明应该选择当前剩余的第num+1大的数,之后在剩余的结果中找第re大的数即可(这里递归一下)。
3. 如果能将阶乘先算出来,就会快很多,觉得实在无聊可以弄一弄,我就不搞了。。。
class Solution{ public: string getPermutation(int n, int k) { visit = vector<bool>(n, false); return DFS(string(), k); } string DFS(string s,int k) { int size = s.size(); int max = factorial(int(visit.size()) - size); int i; if (k == max) {//逆序输出剩余字符 for (i = int(visit.size()); i >= 1; i--) { if (visit[i - 1] == false) s += string(1, i + '0'); } return s; } //计算当前要访问第几个数 int mod = factorial(int(visit.size()) - size - 1); int Remain = k%mod, num = k / mod; if (Remain == 0) {//选择第num个数 int sgn = 0; for (i = 1; i <= int(visit.size()); i++) { if (visit[i - 1] == false) { sgn++; if (sgn == num) { s += string(1, '0' + i); visit[i - 1] = true; } } } //剩余的逆序输出 for (i = int(visit.size()); i >= 1; i--) { if (visit[i - 1] == false) s += string(1, i + '0'); } return s; } else {//选择第num+1个数 int sgn1 = 0; for (i = 1; i <= int(visit.size()); i++) { if (visit[i - 1] == false) { sgn1++; if (sgn1 == num+1) { s += string(1, '0' + i); visit[i - 1] = true; } } } k = k%mod; return DFS(s, k); } } int factorial(int n) { int res = 1; while (n) { res *= n; n--; } return res; } private: vector<bool> visit; }; |