The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
給定一個(gè)數(shù)字n旭贬，求從1到n的第k個(gè)排列蒋畜。
這道題可以用深度優(yōu)先搜索简僧，配合一個(gè)全局計(jì)數(shù)變量解決，但是當(dāng)k較大時(shí)票编，時(shí)間復(fù)雜度會(huì)趨近于n的階乘。
觀察給出的例子，第一位數(shù)子每?jī)煞N組合加1，如果是四個(gè)數(shù)組驮审，就是每6種組合加1，第i位的變化頻次和它后面數(shù)組的組合數(shù)有關(guān)吉执，所以k除以組合數(shù) 就可以求出第一位的數(shù)字疯淫。從數(shù)字list中刪除這個(gè)數(shù)字，更新k值戳玫，可以按此方法求后面的數(shù)字熙掺。
public String getPermutation(int n, int k) {
if (k <= 0 || n <= 0) {
return "";
}
StringBuilder buffer = new StringBuilder();
//n個(gè)數(shù)字的排列數(shù)
int[] cnts = new int[n + 1];
cnts[0] = 1;
for (int i = 1; i <= n; i++) {
cnts[i] = cnts[i-1] * i;
}
List<Integer> nums = new ArrayList<>();
for (int i = 1; i <= n; i++) {
nums.add(i);
}
k--;
while (nums.size() > 0) {
int index = k / cnts[n - 1];
buffer.append(nums.get(index));
k -= index * cnts[n - 1];
nums.remove(index);
}
return buffer.toString();
}