标签：app color 个数 函数 cto stringbu java 数字 append
第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"
思路：观察一下： 我们取k=17。首先数组都是从0开始计数的，所以k-1=16。
从16开始，先可以看出，每一组都是6个数字，n=4,16/(n-1)! =2，也就是数组的第三行的, s[2]。
继续观察，111111 出现了6次，22，33，44都是只出现2次，观察发现出现的次数为(n-1)!
因此得到如下规律 index=k/(n-1)! k%=(n-1)! （k为每一组全排列中为了得到的序号，因此k不断做除法，同时得到下一个更小的全排列）
同时我们取出了每个数字之后，都需要将其删除，因为不能重复出现。
[[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,3,2],[1,4,2,3]
[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,3,1],[2,4,1,3],
[3,2,1,4],[3,2,4,1],[3,1,2,4],[3,1,4,2],[3,4,1,2],[3,4,2,1],
[4,2,3,1],[4,2,1,3],[4,3,2,1],[4,3,1,2],[4,1,3,2],[4,1,2,3]]
c++解法：
class Solution {
public:
string getPermutation(int n, int k) {
string s="123456789";
vectorint> f(n,1); //声明一个初始值都为1，长度为n的数组
string ans;
for(int i=1;i1]*i; //这里用一个vector来表示(n-1)的阶乘
k--;
for(int i=n;i>=1;i--){
int index=k/f[i-1];
k%=f[i-1];
ans.push_backdex]);
s.erase(index,1); //erease 的用法，erase(index,num) num为剔除的个数
}
return ans;
}
小结一下：一开始就想到了这种思路，首先通过vector f(n,1)构造了一个排列组合的数n! ，之后通过找到了索引Index 和下一个更小的全排列的k。index=k/n! ; k=k%(n-1)!
找到了索引之后，因为用过了这个数字就要删除，而c++中的string数组具有删除的功能.
更为简便的是利用STL中的algorithm中的函数next_permutation()，得到下一个全排列
Java版：
class Solution {
public String getPermutation(int n, int k) {
List list=new ArrayList();
StringBuilder sb=new StringBuilder();
for(int i=1;i){
list.add(i);
}
k--;
int fac=1;
for(int i=n;i>=1;i--){
fac=fac*i;
}
for(int i=n;i>=1;i--){
fac/=i; //获得(n-1)!的阶乘
int index=k/fac;
k%=fac;
sb.append(list.get(index));
list.remove(index);
}
return sb.toString();
}
}
leetcode-第k个排列(Java和c++版）
标签：app color 个数 函数 cto stringbu java 数字 append
原文地址：https://www.cnblogs.com/patatoforsyj/p/9682687.html