LC 60 Permutation Sequence(M)

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 k$th$ permutation sequence.

边界条件

解题思路

这道题是让求出n个数字的第k个排列组合，由于其特殊性，我们不用将所有的排列组合的情况都求出来，然后返回其第k个，我们可以只求出第k个排列组合即可，那么难点就在于如何知道数字的排列顺序 http://www.cnblogs.com/grandyang/p/4358678.html

public String getPermutation(int n, int k) {
    int[] fact = new int[n+1];
    int sum = 1;
    List <Integer> num = new ArrayList<Integer>();
    fact[0] = 1;
    //构造一个 阶乘的列表，和 数字的列表
    for(int i = 1; i<=n; i++){
        sum = i* sum;
        fact[i] = sum;
        num.add(i);
    }
    // 转化为数组下标，
    k--;
    StringBuilder sb = new StringBuilder();
    for(int i = 1; i <= n; i++){
        int index = k/fact[n-i];
        sb.append(String.valueOf(num.get(index)));
        num.remove(index);
        k -= index * fact[n-i];
    }
    return sb.toString();
}