Permutation Sequence

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.

题目中给定了一个整数n，它有n的阶乘个全排列，让我们找出第k个全排列。如果我们用回溯法写直到第k个，这样可以找到，但是代价很大，如果k很大时就会超时。我们可以将这些全排列分为n组，第0组是以1开头的，第1组以2开头，一直到第n-1组是以n开头的。这样每组中的全排列数量为(n-1)的阶乘个。我们用k%(n-1)! 这样就知道k属于哪一个组了，从组号就可以得到相应的值。然后让k = k / (n-1)!进行下一次运算。还有一点值得注意的是，为了让k取模后分在正确的组里，k要减1之后运算，例如n为3，k为3或4的时候应该在第二个组，如果直接运算的时候k为3的时候在第二个组，k为4的时候在第三个组。代码如下：

public class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder sb = new StringBuilder();
        List<Integer> list = new ArrayList<Integer>();
        int[] factorial = new int[n];
        factorial[0] = 1;
        for(int i = 1; i < n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }
        for(int i = 1; i <= n; i++) {
            list.add(i);
        }
        k = k - 1;
        for(int i = 0; i < n; i++) {
            int index = k / factorial[n - 1 - i];
            sb.append(list.get(index));
            list.remove(index);
            k = k % factorial[n - 1 - i];
        }
        return sb.toString();
    }
}