Algorithms & Data Structures : LeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number
我自己因為想這題想了很久，所以還是忍不住去看 hint 了。。。羞愧之餘，順手將解答給記錄下來。
解這題前，首先需要會 Next Permutation ，會了之後就會變得相當簡單了。
我的解答：
class Solution {public:void swap(char &a, char &b) {
char t;
t = a;
a = b;
b = t;
}void reverse(int left, int right, string &num) {
while(left <= right) {
swap(num[left], num[right]);
left++;
right--;
}
}void nextPermutation(string &num) { for(int i = num.size() - 1;i >= 1;i--) {
if(num[i] > num[i - 1]) {
int j = num.size() - 1;
while(num[i - 1] >= num[j]) j--;
swap(num[i - 1], num[j]);
reverse(i, num.size() - 1, num);
return;
}
}
reverse(0, num.size() - 1, num);
}int getMinSwaps(string num, int k) {
string new_num = num; // 使用 nextPermutation，我們可以找到距離自己第 K 個的 permutation
for(int i = 0;i < k;i++) {
nextPermutation(new_num);
} // 緊接著，我們可以比對原字串跟距離自己第 K 個的字串
// 看看需要幾步才能從原字串走到新字串
int step = 0;
for(int i = 0;i < num.size();i++) {
if(new_num[i] != num[i]) {
int j;
for(j = i + 1;j < num.size();j++) {
if(new_num[j] == num[i]) {
break;
}
}
for(int k = j;k > i;k--) {
swap(new_num[k], new_num[k - 1]);
step++;
}
}
}
return step;
}
};
大神的解答：
應有更快的解（TODO）
Next Permutation
題目：
這題我當初也沒有想到很有效率的解，最後看解答才知道
時間複雜度：O(N)
空間複雜度：O(1)
的解答。
解答：
class Solution {public:
void swap(int &a, int &b) {
int t = a;
a = b;
b = t;
}
void reverse(int left, int right, vector<int> &nums){
while(left <= right) {
swap(nums[left], nums[right]);
left++;
right--;
}
}
void nextPermutation(vector<int>& nums) {
for(int i = nums.size() - 1;i >= 1;i--) { // 當我們找到 nums[i] > nums[i - 1]
// 代表 nextPermutation 仍存在
if(nums[i] > nums[i - 1]) { // 此時我們可以知道， index : i ~ num.size() - 1 會是一個遞減的陣列
int j = nums.size() - 1; // 從 index : i - 1 的右手邊，挑出恰巧比自己大一點點的元素
while(nums[i - 1] >= nums[j]) j--; // 重點！ 將 nums[i - 1] 與 nums[j] 交換
// 1. nums[i - 1] 會比原本大一些
// 2. index : i ~ nums.size() - 1 仍舊是遞減的陣列
swap(nums[i - 1], nums[j]); // 此時將 index : i ~ nums.size() - 1 通通 reverse
// 會從原本的遞減，變成遞增
reverse(i, nums.size() - 1, nums); // 結果：
// 1. nums[i - 1] 會比原本大一點點
// 2. index : i ~ nums.size() - 1 會變成遞增陣列
// --> 構成 nextPermutation
return;
}
} // 當我們找不到任何 nums[i] > nums[i - 1]
// 則表示現在的陣列已經是遞減的陣列了，沒有 nextPermutation
reverse(0, nums.size() - 1, nums);
}
};
