leetcode60.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):

1."123"
2."132"
3."213"
4."231"
5."312"
6."321"
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

假设按照题中给的排列组合的顺序，假设有1~n个数字，返回第k个排列组合的结果。

思路与代码

首先来整理一下思路。如果有n个数组，则能排列组合出n！个结果。然后再按照排列组合结果的各个位上的数字选择来分析。这里举一个具体的例子。就看题中给的例子，此时n=3。假设k=5。则在百位上，选择的数字为[1，2，3]中的第三个，这是再看十位上的数字，选择了[1,2]中的第一个数。最后在个位上，选择[1]中的第一个。
可以总结出，假设输入n，k，则结果上的从左往右第1位上的数字为结果集中第(k-1)/(n-1)!个数字。这时知道以第1位为开头的结果值有(n-1)!,此时第k个结果集在该位上的选择为k%factorial[n-1]。依次往后类推，直至到最后一位。代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String getPermutation(int n, int k) {
    //factorial
    int[] factorial = new int[]{1,1,2,6,24,120,720,5040,40320,362880};
    
    //初始化
    List<Integer> numbers = new LinkedList<Integer>();
    for(int i = 0 ; i<n ; i++){
        numbers.add(i+1);
    }
    
    StringBuilder result = new StringBuilder();
    k--;
    for(int i = 0 ; i<n ; i++){
        int currentNumber = numbers.remove(k / factorial[n-i-1]);
        result.append(currentNumber);
        k  %=  factorial[n-i-1] ;
    }
    return result.toString();
}