T60. Permutation Sequence【Medium】

題目

集合 [1,2,3,...,n] 包含了 n! 個(gè)不同的排列。

當(dāng) n = 3 時(shí)，有下列的排列組合：

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

給定 n 和 k, 返回第 k 個(gè)序列。

注意：n 在 1~9 之間

思路

大家都知道，n個(gè)數(shù)字有 n! 種排列組合。

但是由于是按順序的，下面代碼的關(guān)鍵在于給結(jié)果分塊。

例如上面的例子：

 "123"
 "132"
 "213"                         "123"  "132" 是一部分
 "231"  按首字母相同，分成三塊 --> "213"  "231" 是一部分
 "312"                         "312"  "321" 是一部分
 "321"

然后這樣繼續(xù)往下分。

所以當(dāng) n 個(gè)數(shù)字就可以分成 n 組有 (n-1)! 種排列組合的部分，然后往下分。

把給出的 （k-1）/（n-1)！ 就得到要找的是在第幾個(gè)部分，同時(shí)也確定了首字母。

例如，上面的例子，k = 4 時(shí)， 代表在第二部分，首字母為 2。

選到第二部分以后，把 k 重新設(shè)置成 2，也就是對(duì)應(yīng)的第二部分的 k 值，對(duì)第二部分重復(fù)剛才的操作，然后就得到了正確的答案。

可能這樣說起來還是有點(diǎn)復(fù)雜，可以 debug 一下代碼看看各個(gè)參數(shù)的變化體會(huì)一下可能會(huì)清晰一些（我就是這樣看才發(fā)現(xiàn)了這代碼想干嘛的/(ㄒoㄒ)/）

代碼

代碼取自 Top Solution，稍作注釋

public String getPermutation(int n,int k){
        int pos = 0;
        List<Integer> numbers = new ArrayList<>();
        int[] factorial = new int[n+1];
        StringBuilder sb = new StringBuilder();
        int sum = 1;
        factorial[0] = 1;
        // 創(chuàng)建一個(gè) {1, 1, 2, 6, 24, ... n!}這樣的數(shù)組
        for(int i=1; i<=n; i++){
            sum *= i;
            factorial[i] = sum;
        }
        // 按順序創(chuàng)建一個(gè){1,2,...n}的數(shù)組
        for(int i=1; i<=n; i++){
            numbers.add(i);
        }
        k--;
        //這里是主要思路,來實(shí)現(xiàn)思路里說的情景
        for(int i = 1; i <= n; i++){
            int index = k/factorial[n-i];
            //找到這個(gè) index 對(duì)應(yīng)的下一個(gè)數(shù)字,添加到 StringBuilder 里面
            sb.append(String.valueOf(numbers.get(index)));
            numbers.remove(index);
            //把 k 減去 index*factorial[n-i],設(shè)置為下個(gè)循環(huán)部分里面對(duì)應(yīng)的 k 的值
            k-=index*factorial[n-i];
        }
        return String.valueOf(sb);
    }