今天是紀錄LeetCode解題的第六十天
是一題困難題

第六十題題目：he 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 for n = 3:

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

Given n and k, return the kth permutation sequence.

此集合[1, 2, 3, ..., n]共包含n!個不同的排列，透過按順序列出所有排列，我們得到以下序列n = 3：
給定n和k，傳回第k個排列序列

解題思路

找出規律
我們觀察此排列可以得出規律，假設n = 4，那麼就有24種排列方式(1234、1243、1324、1342、1423、1432、2134、2143、2314、2341、2413、2431、3124、3142、3214、3241、3412、3421、4123、4132、4213、4231、4312、4321)，我們可以發現第0個位置的數字每6次一組，第1個位置的數字每2次一組，可得出規律為每個位置所出現的次數是(n-1)!次(n在迭代中每次-1)，也就是說第0個位置每(n-1)! = (4-1)! = 6為一組，下一次迭代n-1，所以下一個位置每(3-1)! = 2為一組

計算k在第幾組
假設k = 9，我們可以列出所有排列組合得知第九個排列是2314，在程式當中我們會先計算每幾個次數(idx)為一組，接著迭代i = 1 ~ n + 1，每次計算idx * i，找出當idx * i > k時就表示我的k應該落在哪個排列區間(在找規律當中我們得知一開始idx = 6，當i = 2時，idx * i = 12 > k = 9，此時我們知道第k個組合應該是落在第0個位置為2的排列當中)，接著重新計算k = k - idx * (i - 1)，計算結果為k = 9 - 6 * (2 - 1) = 3，這個新的k還要再去找在第0個位置為2的組合當中第1個位置應該是哪個數字

儲存結果
最後我們把剛剛所迭代的i，對應nums中的數字(nums中儲存1~n)，儲存為res += str(nums[i-1])，並把nums中的該數字移除掉，接著把n - 1準備下一次的計算

程式碼

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        n1 = n
        nums = [i for i in range(1,n+1)]
        res = ""
        while len(nums) > 1:
            idx = 1
            for i in range(1,n):
                idx *= i
            for i in range(1,n1+1):
                if idx * i >= k:
                    k = k - idx * (i-1)
                    res += str(nums[i-1])
                    nums.remove(nums[i-1])
                    n -= 1
                    break
        res += str(nums[0]) #上方執行完會剩最後一個數字把它加入結果
        return res

執行過程(n = 5、k = 60、正確輸出：32541)

初始狀態

• n1 = 5
• nums = [1,2,3,4,5]
• res = " "

計算第0個位置

• idx = 1
• 計算第0個位置幾次為一組：idx = 1 * 2 * 3 * 4 = 24
• i = 1：找落在第幾個組合(也就是計算第0個位置為哪個數字)
• if idx * i >= k → idx = 24 * 1 = 24 >= k = 60 → False
• i = 2 → if idx * i >= k → idx = 24 * 2 = 48 >= k = 60 → False
• i = 3 → if idx * i >= k → idx = 24 * 3 = 72 >= k = 60 → True
• k = k - idx * (i-1) → k = 60 - 24 * (3 - 1) = 12
• res += str(nums[i-1]) → res += str(nums[3 - 1]) → res = "3"
• nums.remove(nums[i-1]) → nums = [1,2,4,5]
• n -= 1 = 4

計算第1個位置

• idx = 1
• 計算第1個位置幾次為一組：idx = 1 * 2 * 3 = 6
• i = 1：if idx * i >= k → idx = 6 * 1 = 6 >= k = 12 → False
• i = 2 → if idx * i >= k → idx = 6 * 2 = 12 >= k = 12 → True
• k = k - idx * (i-1) → k = 12 - 6 * (2 - 1) = 6
• res += str(nums[i-1]) → res += str(nums[2 - 1]) → res = "32"
• nums.remove(nums[i-1]) → nums = [1,4,5]
• n -= 1 = 3

計算第2個位置

• idx = 1
• 計算第2個位置幾次為一組：idx = 1 * 2 = 2
• i = 1：if idx * i >= k → idx = 2 * 1 = 2 >= k = 6 → False
• i = 2 → if idx * i >= k → idx = 2 * 2 = 4 >= k = 6 → False
• i = 3 → if idx * i >= k → idx = 2 * 3 = 6 >= k = 6 → True
• k = k - idx * (i-1) → k = 6 - 2 * (3 - 1) = 2
• res += str(nums[i-1]) → res += str(nums[3 - 1]) → res = "325"
• nums.remove(nums[i-1]) → nums = [1,4]
• n -= 1 = 2

計算第3個位置

• idx = 1
• 計算第3個位置幾次為一組：idx = 1
• i = 1：if idx * i >= k → idx = 1 * 1 = 1 >= k = 2 → False
• i = 2 → if idx * i >= k → idx = 1 * 2 = 2 >= k = 2 → True
• k = k - idx * (i-1) → k = 2 - 1 * (2 - 1) = 1
• res += str(nums[i-1]) → res += str(nums[2 - 1]) → res = "3254"
• nums.remove(nums[i-1]) → nums = [1]
• n -= 1 = 1

跳出while len(nums) > 1迴圈
最後執行res += str(nums[0])，把剩餘在nums裡的1加到res裡，回傳答案res = "32541"