Leetcode題解 Python & C#六月挑戰DAY20 Permutation Sequence

給一個數字 n  代表有 [1,n] 個數字要排列組合，k 代表要找第 k 小的，找出後回傳。

這題一看到時，我想起姊妹題的排列組合找下一個，使用兩兩交換，但這題不是。

這題的限制條件使n最多只有9個，也不重複，因此，使這題可以用規律性去找解法。

如：123 一共有六種組合。

123

132

213

231

312

321

當 k == 3 的時候，第一個數字為2，因為每一個首位數的後面只有2種組合，因些每個首位數字只佔2個，

所以透過除以區間數，就能以商去判斷當前是哪一個數字。

完成了第一步，後面下一個數字能用同樣的模式接上就能解出來了。

如果 k == 3 ，也取了第一個數字 2，剩下的 [1,3] ，可以用分治法的想法去看成子問題︰[1,3] 和 k2 的要找當前數字是什麼。

k2 是多少？因為是 k = 3 所以我們可以預期第二個數字是 1，拿 k2 去除區間大小(1)，得到的商應該是 0 才對，代表從[1,3]取位置[0]出來。

這時有一個問題，是商去決定當前是哪個數，那 k2 應該要是 0 ， 因為 0 除以 1 才會為 0，但 k / 2 = 1...1 ，餘數 1 並沒有對上 k2 去。

為什麼？因為位置系統是以 0 為首，但第 k 小是以 1 為首，所以對不上，因此只要把 k - 1 就能使位置對齊。 

最後，只剩一個要取的數時，後面也沒有組合數了，不能再跑下一個迴圈，就直接把最後一個未取的數補到最後方即可。

Python

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        result = ""
        nums = [str(i) for i in range(1, n+1)]        
        method = [1]
        for i in range(1, n):
            method.append(method[i-1]*i)
        k -= 1
        for i in range(n-1, 0, -1):
            result += nums.pop(k // method[i])
            k = k % method[i]
        result += nums.pop()        
        return result

C#

public class Solution {
    public string GetPermutation(int n, int k) {
        var result = new List();
        var number = new List();
        var factorial = new int[9];
        factorial[0] = 1;
        for(int i = 1; i < n; i ++)
        {
            factorial[i] = factorial[i-1]*i;
            number.Add(i);
        }
        number.Add(n);        
        k -= 1; 
        for(int i = n-1; i > 0; i--)
        {            
            result.Add(number[k / factorial[i]]);
            number.RemoveAt(k / factorial[i]);
            k = k % factorial[i];  
        }         
        result.Add(number[0]);
        return string.Join("", result);
    }
}