这道题目算法上没有什么特别的，更像是一道找规律的数学题目。我们知道，n个数的permutation总共有n阶乘个，基于这个性质我们可以得到某一位对应的数字是哪一个。思路是这样的，比如当前长度是n，我们知道每个相同的起始元素对应(n-1)!个permutation，也就是(n-1)!个permutation后会换一个起始元素。因此，只要当前的k进行(n-1)!取余，得到的数字就是当前剩余数组的index，如此就可以得到对应的元素。如此递推直到数组中没有元素结束。实现中我们要维护一个数组来记录当前的元素，每次得到一个元素加入结果数组，然后从剩余数组中移除，因此空间复杂度是O(n)。时间上总共需要n个回合，而每次删除元素如果是用数组需要O(n),所以总共是O(n^2)。这里如果不移除元素也需要对元素做标记，所以要判断第一个还是个线性的操作。
public class Solution {
public String getPermutation(int n, int k) {
if(k == 0) {
return null;
}
List numList = new ArrayList();
int f = 1;
for(int i=1; i<=n; i++) {
numList.add(i);
f = f*i;
}
f = f/n;
k--;
StringBuffer sb = new StringBuffer();
for(int j=0; j<n; j++) {
int index = k/f;
sb.append(numList.get(index));
numList.remove(index);
k = k%f;
if(j != n-1) {
f = f/(n-j-1);
}
}
return sb.toString();
}
}