Description

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.

Solution

Iteration

很巧妙的找規(guī)律題。假設(shè)n = 4, k = 15，所有可能的permutation則是：

• 1 + {2, 3, 4};
• 2 + {1, 3, 4};
• 3 + {1, 2, 4};
• 4 + {1, 2, 3};

那么每組的組合數(shù)即3! = 6。首先決定第一位，通過15 / 6 = 2，得知第一位應(yīng)該是3。然后題目變成了在{1, 2, 4}中找到k = 15 - 2 * 6 = 3的permutation。
巧妙之處在于用一個candidates list保存尚未被用過的數(shù)字，在每一個迭代中根據(jù)計算出的index去在list中進(jìn)行索引，然后將該數(shù)字移出candidates即可。

class Solution {
    public String getPermutation(int n, int k) {
        int[] factorial = new int[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; ++i) {
            factorial[i] = i * factorial[i - 1];
        }
        
        List<Integer> candidates = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            candidates.add(i);
        }
        
        StringBuilder permutation = new StringBuilder();
        --k;    // important! Because k starts from 1, not 0
        
        for (int i = 0; i < n; ++i) {   // fill ith digit
            int index = k / factorial[n - i - 1];
            permutation.append(candidates.get(index));     // elegant
            candidates.remove(index);
            k -= index * factorial[n - i - 1];
        }
        
        return permutation.toString();
    }
}