Description

Given n and k , return the kth permutation sequence.

Notice

_n _will be between 1 and 9 inclusive.

Example

Forn = 3, all permutations are listed as follows:

"123"
"132"
"213"
"231"
"312"
"321"

Ifk = 4, the fourth permutation is"231"

Solution

以n=4, k=9为例，先找最高位的第一个数，可以从[1, 2, 3, 4]中取，每个数重复3!次。第9个数，按从0开始，就是第8个数，他的第一位数为[1, 2, 3, 4]数组中的第8/3!=8/6=1位，及2. 再继续在剩下的三个数字的permutation中找第8%3!=2个。
可以得到公式：k从k-1开始，nums=[1~n].第1位=k/(n-1)!，再推到=n-1个数的permutation, k = k%(n-1)!，nums把刚确定过得数去掉。

public class Solution {
    /*
     * @param n: n
     * @param k: the k th permutation
     * @return: return the k-th permutation
     */
    public String getPermutation(int n, int k) {
        // write your code here
        int[] nums = new int[n];
        k -= 1;
        int factorial = 1;
        for (int i = 1; i <= n; i++) {
            nums[i-1] = i;
            factorial *= i;
        }

        String result = "";
        for (int i = 0; i < n; i++) {
            factorial /= (n-i);
            int index = k / factorial;
            result += nums[index];
            for (int j = index; j < n - 1; j++) {
                nums[j] = nums[j+1];
            }

            k %= factorial;
        }

        return result;
    }
}