这道题目算法上没有什么特别的，更像是一道找规律的数学题目。我们知道，n个数的permutation总共有n阶乘个，基于这个性质我们可以得到某一位对应的数字是哪一个。思路是这样的，比如当前长度是n，我们知道每个相同的起始元素对应(n-1)!个permutation，也就是(n-1)!个permutation后会换一个起始元素。因此，只要当前的k进行(n-1)!取余，得到的数字就是当前剩余数组的index，如此就可以得到对应的元素。如此递推直到数组中没有元素结束。实现中我们要维护一个数组来记录当前的元素，每次得到一个元素加入结果数组，然后从剩余数组中移除，因此空间复杂度是O(n)。时间上总共需要n个回合，而每次删除元素如果是用数组需要O(n),所以总共是O(n^2)。这里如果不移除元素也需要对元素做标记，所以要判断第一个还是个线性的操作。代码如下：
public String getPermutation(int n, int k) {
if(n<=0)
return "";
k--;
StringBuilder res = new StringBuilder();
int factorial = 1;
ArrayList
nums = new ArrayList
(); for(int i=2;i
=0) { int index = k/factorial; k %= factorial; res.append(nums.get(index)); nums.remove(index); if(round>0) factorial /= round; round--; } return res.toString(); }
上面代码还有有个小细节，就是一开始把k--，目的是让下标从0开始，这样下标就是从0到n-1，不用考虑n时去取余，更好地跟数组下标匹配。如果有朋友有更好的思路来实现线性的时间复杂度，欢迎指教哈，可以留言或者发邮件到linhuanmars@gmail.com给我。