EX:
n = 3, k = 3
"123""132""213""231""312""321"
想法:
看到排列題直覺就是直接使用DFS去列舉全排列直到第K個排列方式，但這題用DFS會超時，因為DFS等於直接列舉出所有可能的排列，因此worst case複雜度會來到O(n!)。
因此這題必須使用其他方法，這邊提供一種網路上看到的巧妙方法，首先觀察全排列可以發現每個數字在每一位出現的次數會是 (n-1)!, n為全部尚未排好的數字，利用這個特點我們可以依序從左至右用 k 去算出第 k 個排列每一位應該是哪個數字，例如: n = 3, k = 3 時，首先第一位數字 1,2,3 分別會依序出現2次(i.e. (n-1)! )，n = 3 時每個數字在第一位數重複兩次(2!)，固定第一位數後，剩下的數字在第二位數重複一次(1!)，所以可以得知第 3 個排列的第一位數字一定是 "2" , (k / 2!)，固定第一位數為2之後，剩下的數字(1, 3)在第二位數皆只會重複一次(231 or 213)，而第一位數為2且第一位數重複次數為2因此以2開頭的排列至少是第3個排列之後的，因此(k - 2) = 1，第二位數每個剩下的數字重複一次且 k = 1，因此第二位數為 "1"，固定一二位數之後，第三位數剩下的每個數字重複次數為 1 次(0!)，且剩餘一個數字因此第三位數為"3"。
位數 1 2 3
每個數字出現次數 2 1 1
可以導出規律如下:
a1 = k / (n - 1)!
k1 = k
a2 = k1 / (n - 2)!
k2 = k1 % (n - 2)!
...
an-1 = kn-2 / 1!
kn-1 = kn-2 % 1!
an = kn-1 / 0!
kn = kn-1 % 0!
Time Complexity: O(n)
完整程式碼:
解法一: DFS
class Solution {
public:
string res;
void dfs(string& cur, int n, int k, int& depth, vector<bool>& used) {
if (depth > k) { return; }
if (cur.size() == n) {
depth++;
if (depth == k) {
res = cur;
}
return;
}
for (int i = 1; i <= n; i++) {
if (used[i]) { continue; }
cur.push_back(i + '0');
used[i] = true;
dfs(cur, n, k, depth, used);
used[i] = false;
cur.pop_back();
}
}
string getPermutation(int n, int k) {
string cur;
vector<bool> used(n+1, false);
int depth = 0;
dfs(cur, n, k, depth, used);
return res;
}
};
解法二:
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> fact(n + 1);
// 紀錄 1 ~ 9 的字元
string nums;
// 紀錄 n! 的值
fact[0] = 1;
for (int i = 1; i <= n; i++) {
fact[i] = i * fact[i - 1];
nums.push_back(i + '0');
}
string res;
// 每次計算目前的最高位
while (n > 0) {
// 考慮邊界情況，若用 k / fact[n-1] 則若 k == fact[n-1] 會出錯，應該取 0 而非 1
int cur = (k - 1) / fact[n - 1];
res += nums[cur];
// 每個數字只能使用一次，因此把用過得刪掉
nums.erase(nums.begin() + cur);
// 計算次高位要取第幾個，因為到目前的最高位為止已經保證是第 cur * fact[n - 1] 位之後，因此只要在找接下來的第 k - cur * fact[n-1] 位。
k -= cur * fact[n - 1];
// 計算次高位
--n;
}
return res;
}
};
沒有留言:
張貼留言