60. 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=4，则有{1, 2, 3, 4}。 若列出所有的permutations，为：

1 + (permulations of 2, 3, 4)

2 + (permulations of 1, 3, 4)

3 + (permulations of 1, 2, 4)

4 + (permulations of 1, 2, 3)

三个数字的permutation个数为3！，因此我们可以找到第一个digit的index，为k/3!，假设为2（即数字3）。 接下来，我们找第二个digit，

1 + (permulations of 2, 4)

2 + (permulations of 1, 4)

4 + (permulations of 1, 2)

这时我们需要找第k=k%3!个，因此第二个digit的index为k/2!。

之后的都以此类推。

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