Permutation Sequence 388

Question

Given n and k, return the k-th permutation sequence.

Notice

n will be between 1 and 9 inclusive.

Example

For n = 3, all permutations are listed as follows:

"123"

"132"

"213"

"231"

"312"

"321"

If k = 4, the fourth permutation is "231"

Challenge

O(n*k) in time complexity is easy, can you do it in O(n^2) or less?

Solution

先将所有可用的数字（1-n）存入一个list，每用掉一个数就将其从list中删去。

idea: 以某一数字开头的排列有(n-1)! 个。例如： 123， 132， 以1开头的是 2！个。

1) 第一位数字可以用(k-1)/(n-1)!来计算，相当于一轮(（n-1）!)就换一个数，看有几轮就是第几个数。这里用k-1是为了在边界条件时计算正确，例如k正好等于(n-1)!，则应该是第0轮的最后一个数，所以应该取第0个数，但如果直接用k/(n-1)!得到的是1，所以一开始要用k-1，这样边界时的计算才是正确的。

2) 剩下的k为(k-1)%(n-1)!。

3) 重复第一步，用新的k来计算第二位的数。此时每一轮的大小应该变为(n-2)!，用k/(n-2)!来得到在剩下可用的数中要取第几位数。

4) 重复1-3直到所有可用的数字用尽。

代码如下：

class Solution {
    /**
      * @param n: n
      * @param k: the kth permutation
      * @return: return the k-th permutation
      */
    public String getPermutation(int n, int k) {
        ArrayList<Character> digits = new ArrayList<Character>();
        for(char i = '1'; i < '1' + n; i++){
            digits.add(i);
        }

        int factor = 1;
        for(int i = 1; i <= n; i++){
            factor *= i;
        }

        StringBuilder sb = new StringBuilder();
        k = k - 1;
        int count = n;
        while(!digits.isEmpty()){
            factor /= count;
            count--;
            int index = k / factor;
            k = k % factor;
            sb.append(digits.get(index));
            digits.remove(index);
        }
        return sb.toString();
    }
}