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.
一刷
题解：
如果一上来使用了backtracking的方法依次构造出排列数，当然结果不出所料的TLE了。实际上，仔细观察这些数字，我们还是不难发现一些规律的。
假设有四位数字{1， 2， 3， 4}，那么他们能够产生的排列数是什么呢？
1 + {2, 3, 4}
2 + {1, 3, 4}
3 + {1, 2, 4}
4 + {1, 2, 3}
其实就是选定第一位数字后，其他剩下的数字进行排列组合，就能求出以该数字打头的所有排列组合。想必已经能发现一些规律了，我们干脆再举一个具体的例子，比如我们现在想要找第14个数，那么由于14 = 6 + 6 + 2。因此第一个数打头的是3，然后再求{1, 2, 4}中第二个排列组合数，答案是"142"。所以最终答案就是"3142"啦。
这里有一些问题是需要我们注意的：
构造排列数从最高位开始，当选出一个数字后，就应当把这个数字erase掉，防止后面又出现；
我们所要求的第k个数需要在每次循环中减去对应的值；
注意程序中的数组是从0开始的，但题目的输入是从1开始计数的。
题解中最巧妙的是使用了linkedlist, k--，这样k / (n - 1)!就对应着从0 ~ （n - 1）这n个group，这个结果也是我们linkedlist中取出元素的index。接下来进行 k % = (n - 1)!后， k又继续对应 0 ~ (n - 2)这个 n - 1个group。非常好用。
public class Solution {
public String getPermutation(int n, int k) {
if(n<=0 || k<=0) return "";
List<Integer> nums = new LinkedList<>();
int factorial = 1;
for(int i=1; i<=n; i++){
factorial *=i;
nums.add(i);
}
StringBuilder sb = new StringBuilder();
k--;
while(n>0){
factorial /=n;//(n-1)!
sb.append(nums.remove(k/factorial));//remove 0->nums[0] = 1;
k %= factorial;
n--;
}
return sb.toString();
}
}
二刷
由于完全不记得了，这回从一个简单的方法开始。
- 首先构造factorial的lookup表。例如n=4, 则factorial = [1,1,2,6,24], 长度为5， factorial[n] = n!
- 然后构造所含的数字集合，numbers = {1,2,3,4}，因为每次选择了一个数字之后要将它从集合中取出。
- 注意，k--
然后再从第n位开始逐步选择所需的digit
public class Solution {
public String getPermutation(int n, int k) {
int[] factorial = new int[n+1];
List<Integer> numbers = new ArrayList<>();
StringBuilder sb = new StringBuilder();
factorial[0] = 1;
for(int i=1; i<=n; i++){
factorial[i] = factorial[i-1]*i;
}
for(int i=1; i<=n; i++){
numbers.add(i);
}
k--;
for(int i=1; i<=n; i++){//1 to n th number
int index = k/factorial[n-i];
int num = numbers.get(index);
sb.append(String.valueOf(num));
numbers.remove(index);
k -= index*factorial[n-i];
}
return sb.toString();
}
}
