【LeetCode 60】第k个排列
LeetCode 排列 60
2023-09-14 09:03:43 时间
【题解】
逆康托展开。 考虑康托展开的过程。 K = ∑v[i]*(n-i)! 其中v[i]表示在a[i+1..n]中比a[i]小的数字的个数 (也即未出现的数字中它排名第几(从0开始)) 那么我们在逆康托展开的时候,就可以通过直接除(n-i)!得到每个数字的v[i]的值。 然后通过给已经出现的数字打tag。 剩下的问题就转化为找未出现的第v[i]个数字了。 注意康托展开的值是比当前序列小的序列的个数。 所以如果要找序号为k的序列的话,实际上应该找k-1对应的逆康托序列【代码】
class Solution {
public:
string getPermutation(int n, int k) {
int fac[10],tag[10];
memset(tag,0,sizeof(tag));
int a[10];
fac[0] = 1;
for (int i = 1;i <= 9;i++) fac[i] = fac[i-1]*i;
k--;
for (int i = 1;i <= n;i++){
for (int j = 1,l=k/fac[n-i];j<=n;j++){
if (tag[j]==0){
l--;
if (l<0){
a[i] = j;
tag[j] = 1;
break;
}
}
}
k=k%fac[n-i];
}
string s ="";
for (int i = 1;i <= n;i++){
s = s+(char)(a[i]+'0');
}
return s;
}
};
相关文章
- ☆打卡算法☆LeetCode 210. 课程表 II 算法解析
- Longest Common Prefix_LeetCode
- 【leetCode】整数反转
- LeetCode–046–全排列(java)
- Leetcode题目078-子集
- leetcode刷题(131)——背包问题理解
- LeetCode 1051. 高度检查器
- LeetCode 905. 按奇偶排序数组
- LeetCode 第3题 无重复字符的最长子串(小白详解)
- JavaScript刷LeetCode拿offer-二叉树层序遍历篇_2023-02-28
- JavaScript刷LeetCode模板技巧篇(一)2
- 【链表篇】LeetCode 876、链表的中间结点
- C 语言的 LeetCode 30 天挑战 第1部分,共10部分