[LeetCode] 60. Permutation Sequence

轉自LeetCode

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.

<Solution>

因為是 LeetCode，所以不能傻傻的真的去排列到要求的第 K 個，一定 TLE

那要怎麼快速找到，這時候就要觀察規律了(參考資料)

用 n = 4, k = 14 說明

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142  <-- k = 14
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

題目有說 n 是從 1 到 9，那先準備一個 string nums = "123456789"

從上面可以看到，第一位數字出現的累積次數為 3! = (4 - 1)! = (n - 1)! = 6

第二位數字出現的累積次數為 2! = (4 - 2)! = (n - 2)! = 2

因此可以將 k / 累積次數來知道 k 會落在哪個數字

但配合 string 的 index 從 0 開始，所以改成 (k-1) / 6，以下是分解動作

• 第一位數的 index = (k-1) / (n-1)! = (14 - 1) / 3! = 13 / 6 = 2

nums[2] = 3，這時候 3 用掉了，從 nums 拿掉 => nums = "12456789"

• k' = (k-1) % 3! = (14 - 1) % 6 = 1，第二位數的 index = k' / (n-2)! = 1 / 2! = 0

nums[0] = 1，這時候 1 用掉了，從 nums 拿掉 => nums = "2456789"

• k'' = k' % 2! = 1 % 2 = 1，第三位數的 index = k'' / (n-3)! = 1 / 1! = 1

nums[1] = 4，這時候 4 用掉了，從 nums 拿掉 => nums = "256789"

•  k''' = k'' % 1! = 1 % 1 = 0，第四位數的 index = 0 / (n-4)! =  0 / 1 = 0

nums[0] = 2，這時候 2 用掉了，從 nums 拿掉 => nums = "56789"

• 於是最後的答案就是 3142

code 如下
c++

kotlin