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.

看到这道题，第一时间就联系到了. 那道题是让找下一个稍大的Permutation, 而这里是找从小到大第K大的Permutation, 而最小的Permutation我们明显知道，那么用Next Permutation做Subroutine，做K次，不就找到了所需的Permutation了吗。Next Permutation时间复杂度为O(N), 这里就是O(N*k).

代码里面把Int数组拷贝成一个char数组，是为了方便转换成String。int[]数组是不能直接作为new String(array)的argument的。另一方面，这道题再次证实了数组是对象，而函数用对象做argument传的是对该对象的引用，在函数内改引用不会对原数组造成影响，但是在函数内改引用所指向的内容，就会有影响了。比如这里传数组num，而里面改num[i], 改的是内容，所以num改变了

1 public class Solution { 2     public String getPermutation(int n, int k) { 3         char[] array = new char[n]; 4         for (int i=0; i
     
      =0; i--) {17             if (array[i] < array[i+1]) break;18         }19         if (i >= 0) {20             for (j=i; j
     

我这个方法很直接，但是时间复杂度O(N*k)应该比较大，因为k是可以取值到N!的，虽然通过了OJ，但是还是不太好。 网上看到一些做法，均是把它当做一道找规律的数学题目。我们知道，n个数的permutation总共有n阶乘个，基于这个性质我们可以得到某一位对应的数字是哪一个。思路是这样的，比如当前长度是n，我们知道每个相同的起始元素对应(n-1)!个permutation，也就是(n-1)!个permutation后会换一个起始元素。因此，只要当前的k除以(n-1)!，得到的数字就是当前的index，如此就可以得到对应的元素，而k % (n-1)! 得到的数字就是当前剩余数组的index，如此递推直到数组中没有元素结束。实现中我们要维护一个数组来记录当前的元素，每次得到一个元素加入结果数组，然后从剩余数组中移除，因此空间复杂度是O(n)。时间上总共需要n个回合，而每次删除元素如果是用数组需要O(n),所以总共是O(n^2)。这里如果不移除元素也需要对元素做标记，所以要判断第一个还是个线性的操作。

第二遍做法：

LISHI's

We actually can calculate the sequence. For sequences with n numbers, it is composed by n segments of sequences with n-1 numbers. The number of (n-1) sequences in each segment is (n-1)!. So if we are looking for kth n sequence, it is in (k/(n-1)!)th or (k/(n-1)!+1)th segment (boundary case considerred) which is means the number in the first place should be the (k/(n-1)!)th available number between 1 and n. The number of sequences we should count in this segment to find the target is (k%(n-1)!)th sequence in this segement. With this recurrence formula, we can directly calculate the string one place by one place.

1 public class Solution { 2     public String getPermutation(int n, int k) { 3         if (n<=0 || k<=0) return ""; 4         StringBuffer res = new StringBuffer(); 5         int factorial = 1; 6         for (int i=2; i
     
       num = new ArrayList
      
       ();10         for (int i=1; i<=n; i++) {11             num.add(i);12         }13         int round = n - 1;14         k--;15         while (round >= 0) {16             int index = k / factorial;17             k %= factorial;18             res.append(num.get(index));19             num.remove(index);20             if (round > 0) {21                 factorial /= round;22             }23             round--;24         }25         return res.toString();26     }27 }
      
     

说明：num数组中按顺序存着1-n这n个数；每找到一个index，把它加入res的同时，把该index元素从数组删除. 这样不会重复利用某个数组元素

k--目的是让下标从0开始，这样下标就是从0到n-1，更好地跟数组下标匹配（这样每(n-1)!个数它们的第一个元素都是一样的）。

factorial最开始是（n-1）！，然后（n-2）！。。。跟数组剩余元素个数有关（每次减一）

因为答案有n位，所以round有n轮，一轮确定一位数。这里因为正好factorial要依次除n-1, n-2, n-3...所以干脆就让round计数从n-1到0