LeetCode刷题记录 - 60.第k个排列
程序员文章站
2022-01-15 11:59:40
...
执行用时:4ms
语言:cpp
思路:和求十进制数各位数类似,用k/(n-1)!判断每一位是该位的第几轮排列,再让k%(n-1)!计算下一位
代码:
class Solution {
public:
string getPermutation(int n, int k) {
int m = fac(n);
string res = "";
vector<int> tb;
for(int i = 1;i <= n;i++){
tb.push_back(i);
}
int i = n -1;
k--;
while(i > 0){
int t = fac(i);
int j = k / t;
char c = (tb[j] + '0');
res += c;
tb.erase(tb.begin()+j);
k %= t;
i--;
}
res += (tb[0] + '0');
return res;
}
private:
int fac(int n){
int res = 1;
for(int i = 2;i <= n;i++){
res *= i;
}
return res;
}
};
推荐阅读
-
#leetcode刷题之路25- k个一组翻转链表
-
#leetcode刷题之路19-删除链表的倒数第N个节点
-
#leetcode刷题之路23-合并K个排序链表
-
LeetCode刷题记录——第122题(买卖股票的最佳时机二)
-
#leetcode刷题之路31-下一个排列
-
LeetCode 刷题 [C++] [面试题 17.09]. 第 k 个数 (动态规划 + 三指针)
-
#leetcode刷题之路25- k个一组翻转链表
-
Leetcode刷题java之23. 合并K个排序链表(一天一道编程题之四十天)(优先队列)
-
#leetcode刷题之路19-删除链表的倒数第N个节点
-
为面试准备,每天刷题@leetcode_面试题 02.02. 返回倒数第 k 个节点