python3 解法, 执行用时: 1020 ms, 内存消耗: 15.1 MB, 提交时间: 2022-12-03 13:46:21

'''
这题可以分成两部分，第一部分寻找第k个最小妙数，第二部分将原先的数组转换为寻找到的最小妙数，需要交换的最小次数。
第一部分我们定义一个函数寻找下一个最小妙数，然后执行k次，就是我们要寻找的最小妙数了。
'''
class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:

        def findnext_nums(nums):
            for i in range(n-1,0,-1):
                if nums[i-1] < nums[i]:   #找到后面数字比前面数字大的情况，不加这行会导致超时，具体情况可以试试
                    for j in range(n-1,i-1,-1):   #从后往前遍历到索引i-1的前面
                        if nums[i-1] < nums[j]:   #从后往前找到数字比nums[i-1]大的数字
                            nums[i-1],nums[j] = nums[j],nums[i-1]    #交换这两个数字
                            nums[i:] = sorted(nums[i:])       #将i-1之后的数子排序，因为这样才是最小妙数
                            return nums

        n = len(num); nums = list(num); num = list(num)
        for _ in range(k):
            nums = findnext_nums(nums)
        
        cnt = 0
        for i in range(n):
            if num[i] != nums[i]:  #如果这两个数组的数字不相等
                for j in range(i+1,n):
                    if num[j] == nums[i]:    #从原数组往后找，找到和现数组相等的数
                        cnt += j-i           #两个索引的差就是交换次数
                        num[i+1:j+1] = num[i:j]    #将原数组两个索引对应的位置前进一格，也就是交换的结果
                                                   #不过原数组的i没有替换，但并不影响后面
                        break
        return cnt

cpp 解法, 执行用时: 32 ms, 内存消耗: 7.4 MB, 提交时间: 2022-12-03 13:45:14

class Solution {
public:
    int getMinSwaps(string num, int k) {
        const int n = num.size();
        // 第 k 个妙数
        string per = num;
        for (int i = 0;i < k;++i)
            next_permutation(per.begin(), per.end());
        // 进行下标映射
        vector<int> map[10];
        for (int i = 0;i < n;++i)
            map[num[i] - '0'].push_back(i);
        int idx[10] = {};
        vector<int> arr(n);
        for (int i = 0;i < n;++i)
            arr[i] = map[per[i] - '0'][idx[per[i] - '0']++];
        // 树状数组求逆序对个数 O(nlogn)
        vector<int> tree(n + 1);
        int ans = 0;
        for (int i = n - 1;0 <= i;--i) {
            for (int j = arr[i];j > 0;j -= j & -j) ans += tree[j]; // 查询
            for (int j = arr[i] + 1;j <= n;j += j & -j) ++tree[j]; // 更新
        }
        return ans;
    }
};

cpp 解法, 执行用时: 20 ms, 内存消耗: 6.4 MB, 提交时间: 2022-12-03 13:44:20

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

python3 解法, 执行用时: 1528 ms, 内存消耗: 15 MB, 提交时间: 2022-12-03 13:44:02

'''
第一步我们需要求出比num 大的第 k 个排列 numk。

第二步我们需要将 num 通过交换操作得到 numk，每一步交换操作只能交换相邻的两个字符。
 '''
class Solution:
    def getMinSwaps(self, num: str, k: int) -> int:
        def nextPermutation(num: List[str]) -> None:
            i = len(num) - 2
            while i >= 0 and num[i] >= num[i + 1]:
                i -= 1
            if i >= 0:
                j = len(num) - 1
                while j >= 0 and num[i] >= num[j]:
                    j -= 1
                num[i], num[j] = num[j], num[i]

            left, right = i + 1, len(num) - 1
            while left < right:
                num[left], num[right] = num[right], num[left]
                left += 1
                right -= 1
        
        num = list(num)
        num_k = num[:]
        
        for i in range(k):
            nextPermutation(num_k)
        
        n = len(num)
        ans = 0
        
        for i in range(n):
            if num[i] != num_k[i]:
                for j in range(i + 1, n):
                    if num[j] == num_k[i]:
                        for k in range(j - 1, i - 1, -1):
                            ans += 1
                            num[k], num[k + 1] = num[k + 1], num[k]
                        break
        
        return ans