原题
给出集合 [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"
解法
思想
对于第一位,任一数字所占个数就是n-1
的阶乘,那么可以通过先计算出1~n-1
的阶乘,然后每一位按顺序递推。
代码
class Solution {
public String getPermutation(int n, int k) {
StringBuilder sb = new StringBuilder();
boolean[] used = new boolean[n];
int factorial[] = new int[n];
int count = 1;
factorial[0] = 1;
k -= 1;
for(int i = 1; i < n;i++){
factorial[i] = (count*=i);
}
for(int num = n-1;num >= 0 ; num--){
int pos = k / factorial[num];
k %= factorial[num];
for(int i = 0;i<n;i++){
if(!used[i]){
if(pos == 0) {
sb.append(i+1);
used[i] = true;
break;
}
pos -= 1;
}
}
}
return sb.toString();
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode60-%e7%ac%ack%e4%b8%aa%e6%8e%92%e5%88%97/