Minimum Adjacent Swaps to Reach the Kth Smallest Number

给一个数组, 求做完下k次permutation后数组通过几个swap能变回原数组.

这题就是先做k permutation, 然后比较两个数组的不同位置, 找到同样的数字后, swap回来, 因为求的是minimum swap, 所以如果数字相同的情况下, 只要找最邻近做swap即可.

class Solution {
public:
    int getMinSwaps(string num, int k) {
        string v(num);
        while(k > 0){
            next_permutation(v.begin(), v.end());
            k--;
        }
        int res = 0;
        for(int i = 0 ; i < v.size(); i++){
            if(num[i] != v[i]){
                int j = i + 1;
                while(j < v.size()){
                    if(num[j] == v[i]){
                        break;
                    }
                    j++;
                }// find j 
                for(; j > i; j--){
                    swap(num[j], num[j - 1]);
                    res++;
                }
            }
        } 
        return res;
    }
};