1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number

首先我們得先搞定permutation

c++有function可以用, 但以防萬一我們還是要知道怎麼實作

可參考 leetcode 31

但是countStep這邊我還是看不太明白, 這原理怎麼可以這樣用

class Solution {
public:
    void nextPermutation(string &s){
        if(s.size() == 0 || s.size() == 1) return;
        int k = s.size() - 2;
        for(; k >= 0; k--){
            if(s[k] < s[k + 1]) break;
        }
        if(k < 0){
            reverse(s.begin(), s.end());
            return;
        }
        int l = s.size() - 1;
        for(; l >= 0;l--){
            if(s[l] > s[k]) break;
        }
        swap(s[l], s[k]);
        reverse(s.begin() + k + 1, s.end());
    }
    int countStep(string &s1, string &s2){
        int size = s1.size();
        int i = 0, j = 0;
        int result = 0;
  
        while (i < size) {
            j = i;
            while (s1[j] != s2[i]) j++;
   
            while (i < j) {
                swap(s1[j], s1[j-1]);
                j--;
                result++;
            }
            i++;
        }
        return result;
    }
    int getMinSwaps(string num, int k) {
        string ori = num;
        while(k>0){
            nextPermutation(num);
            k--;
        }
        return countStep(ori, num);
        
    }
};