📘 題目敘述
給定整數 n 和 k。
集合 [1, 2, 3, ..., n] 總共有 n! 種不同排列。
如果把這些排列按照字典序全部列出來，請回傳第 k 個排列字串。
條件限制
1 <= n <= 91 <= k <= n!
🧠 解題思路
我這題的想法不是把所有排列真的列出來，而是直接判斷第 k 個排列在每一位應該放什麼數字。
關鍵在於：
如果第一位固定之後，後面剩下的排列數量會是固定的。
例如剩下 n - 1 個數字時，後面總共有 (n - 1)! 種排法。
所以我可以用 (k - 1) / (n - 1)! 判斷：
- 這一位應該選目前還沒用過的第幾小數字
接著把前面那一整塊排列數量扣掉，再繼續處理下一位。
這樣每次決定一個位置，最後就能直接組出第 k 個排列。
所有變數
s：最後要組出來的答案字串a：預先存好的階乘表，a[i]代表i!b：記錄哪些數字已經被使用過m：目前這一位要選「第幾個還沒用過的數字」
🪜 主要流程步驟
1. 先準備階乘表和使用狀態
我先準備一個階乘陣列 a：
int a[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
這裡的意思是：
a[0] = 1a[1] = 1a[2] = 2a[3] = 6- ...
也就是把 0! 到 8! 先存好，後面就能直接拿來用。
我也準備一個布林陣列 b：
bool b[9] = {false};
它用來記錄 1 到 9 這些數字目前有沒有被選過。
如果 b[i] == true，就表示數字 i + 1 已經放進答案裡了，不能再用。
2. 每次先決定目前這一位要選第幾個可用數字
當還有 n 個位置沒填時，固定目前這一位之後，後面還會剩 n - 1 個數字可以排列。
所以每一大塊的大小就是 (n - 1)!，也就是 a[n - 1]。
因此我用：
int m = (k - 1) / a[n - 1];
來判斷這一位應該選哪一個數字。
這裡要特別注意我用的是 k - 1，原因是：
- 題目的
k是從1開始編號 - 但這種分塊判斷比較適合用從
0開始的想法
所以先減一之後，m 就會表示：
- 目前這一位要選「第
m個還沒被使用的數字」
3. 扣掉前面整塊排列數量，更新下一輪的 k
決定完目前這一位要落在哪一塊之後，
我就把前面那些整塊的排列數量扣掉：
k -= m * a[n - 1];
這一步的意思是：
- 前面
m塊都已經被跳過了 - 接下來我要在目前選中的這一塊裡，繼續找下一位
所以更新完之後的 k，就是「在這一小塊裡面」的第幾個排列。
4. 從還沒用過的數字裡，找到第 m 個
接著我就從小到大掃過所有數字，找目前還沒被使用過的那些數字。
- 如果這個數字還沒被用過，才有資格被選
- 如果
m > 0，表示還沒走到我要的那一個可用數字，所以先略過，並把m減一 - 當
m == 0時，表示現在這個就是我要選的那個數字
這時候我就把 i + 1 加到答案字串 s 裡，
並且把 b[i] 設成 true，表示這個數字之後不能再用了。
5. 選完一位之後，繼續處理下一位
每成功選完一個數字之後，我就把 n 減一
這代表：
- 已經少了一個位置要填
- 也少了一個數字可以用
接著再進下一輪，重新根據新的 n 和新的 k 去決定下一位。
這樣一路做下去，直到所有位置都填完為止。
6. 最後回傳組好的排列字串
當 while (n > 0) 結束時，表示每一位都已經選好了。
這時候 s 裡面就是第 k 個排列，直接回傳即可。
⏱️ 複雜度
設原本輸入的數字為 n。
- 時間複雜度：
O(n^2)
一共要決定n個位置，而每次都可能掃一遍尚未使用的數字。 - 空間複雜度：
O(n)
答案字串和使用狀態都會隨著n增加。
💻 程式碼實作
class Solution {
public:
string getPermutation(int n, int k) {
string s;
int a[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
bool b[9] = {false};
while (n > 0) {
int m = (k - 1) / a[n - 1];
k -= m * a[n - 1];
for (int i = 0; i < 9; i++) {
if (!b[i]) {
if (m > 0) {
m--;
continue;
}
s += to_string(i + 1);
b[i] = true;
break;
}
}
n--;
}
return s;
}
};
🔗 題目連結
https://leetcode.com/problems/permutation-sequence/