Hard題, 我個人認為暴力的dfs其實也是需要一點巧思的, 不是那們簡單的
我們會先列一個陣列, 倘若有走到就是設1, 當pop出來之後再改回0
就這樣我們可以每次都讓不同的人當頭, 然後在往後一個一個擺, 用說明的其實相對不容易, 可以紙筆推導一下
然後最後只要找到target的number, 即可退出
這題好心的地方在於暴力解是可以過的
class Solution {
public:
bool helper(vector<int>& vis, vector<int>& res, int &number, int target){
if(res.size() == vis.size()){
if(++number == target){
return true;
}
return false;
}
for(int i = 1; i <=vis.size();i++){
if(vis[i - 1] > 0) continue;
vis[i - 1] = 1;
res.push_back(i);
bool next = helper(vis, res, number, target);
if(next) return true;
res.pop_back();
vis[i - 1] = 0;
}
return false;
}
string getPermutation(int n, int k) {
vector<int> vis(n, 0);
vector<int> res;
int number = 0;
helper(vis, res,number, k);
string ans;
for(auto n :res){
ans+=to_string(n);
}
return ans;
}
};但是這樣時間複雜度就是O(n!), 有沒有辦法用更快的呢
其實有的, 但我覺得不容易想到
因為是有序的, 我們可以發現
123
132
213
231
312
321可以注意到, 最前面的數字總共有三組, 我們可以先看k在哪一組
而到底有幾組呢, 就是(n -1)!組, 所以以此類推, 我在決定往後的k在哪一組, 就是 (n-1)!, (n-2)!, …0!
然後組別中, 用過的數字我們就把後方的數字往前移動, 來讓下一組的順序可以對到正確的數字
class Solution {
public:
string getPermutation(int n, int k) {
vector<int> num;
vector<int> order(10, 1);
order[0] = 1;
for (int i = 1; i <= 9; i++) {
num.push_back(i);
order[i] = order[i - 1] * i;
}
string s;
k--;
while (n > 0) {
n--;
int d = k / order[n];
k %= order[n];
s += ('0' + num[d]);
for(int i = d + 1; i <= 9;i++){
num[i- 1] = num[i];
}
}
return s;
}
};簡單記錄一下
