5749. 邻位交换的最小次数

难度 medium
给你一个表示大整数的字符串 num ，和一个整数 k 。

如果某个整数是 num 中各位数字的一个 排列 且它的 值大于 num ，则称这个整数为 妙数 。可能存在很多妙数，但是只需要关注 值最小 的那些。

例如，num = "5489355142" ：
第 1 个最小妙数是 "5489355214"
第 2 个最小妙数是 "5489355241"
第 3 个最小妙数是 "5489355412"
第 4 个最小妙数是 "5489355421"
返回要得到第 k 个 最小妙数 需要对 num 执行的 相邻位数字交换的最小次数 。

测试用例是按存在第 k 个最小妙数而生成的。

示例 1：

输入：num = "5489355142", k = 4
输出：2
解释：第 4 个最小妙数是 "5489355421" ，要想得到这个数字：

• 交换下标 7 和下标 8 对应的位："5489355142" -> "5489355412"
• 交换下标 8 和下标 9 对应的位："5489355412" -> "5489355421"
  示例 2：

输入：num = "11112", k = 4
输出：4
解释：第 4 个最小妙数是 "21111" ，要想得到这个数字：

• 交换下标 3 和下标 4 对应的位："11112" -> "11121"
• 交换下标 2 和下标 3 对应的位："11121" -> "11211"
• 交换下标 1 和下标 2 对应的位："11211" -> "12111"
• 交换下标 0 和下标 1 对应的位："12111" -> "21111"
  示例 3：

输入：num = "00123", k = 1
输出：1
解释：第 1 个最小妙数是 "00132" ，要想得到这个数字：

• 交换下标 3 和下标 4 对应的位："00123" -> "00132"

提示：

2 <= num.length <= 1000
1 <= k <= 1000
num 仅由数字组成

解题思路：这道题目是21年5月2号参与leetcode周赛的第3道题目，我还是没做出来，后来看到题解就释然了，感觉这个难度还是挺大的，不是一般的中等难度的题目，还是很佩服那些比赛时候能写出答案的人，我赛后琢磨了两三个小时，参考了其他的一些题目才想清楚的。
思路是这样的，这道题目应该分成两道小题来做，一是获取k个next permutation，这个功能是另一道leetcode题目31. 下一个排列中完成的，我们只要循环k次，就可以获取next k permutation，然后我们把结果保存起来，计算从origin的数组转换到第k个permutation要经过多少次交换，这里又是另一道leetcode的题目，我找不到原题，但leetcode官方题解是这样说的，这是另一道计算交换次数的题目。leetcode官方题解给了挺详细的证明，大意就是，我们需要找到origin转换到next k permutation（记为temp）的最小交换次数，遍历origin数组，如果origin[i]!=temp[i]，则往后遍历origin，找到与temp[i]相等的数，然后从遍历的起点到origin[j]和temp[i]相等这个地方，进行相邻元素的交换，最后把origin[j]换到遍历的起点去，结果就是temp[i]和origin[i]相等，然后不断重复这个过程，直到origin遍历完整个数组，交换过程中记录交换次数res，最后返回。为什么这个结果就是最小交换次数？假设temp中所有元素互不相等，我们给它进行重映射，temp中的元素依次映射为1,2,...,n,origin也要进行相应的元素重映射，origin要交换直到变成temp这个样子，最后的逆序数应该为0，在每次交换中，如果temp[i]<temp[i+1]，temp的逆序数会增加1，如果temp[i]>temp[i+1]，逆序数会减少1，我们前面讲到的交换过程，其实就是减少逆序数的过程，因为我们在某个位置i比较origin[i]和temp[i]是否相等的时候，根据我们的方法，可知在idx<i的位置，都有origig[idx]=temp[idx]，逆序数已经变为0了，因此idx>i的地方，我们每进行一次交换，都是将逆序数减小，没有增加的步骤，因此按照上面这种方法处理，最后得到的交换次数就是最小的交换次数。如果temp中有相同的元素，结果也是一样的，参考leetcode官方题解的证明。

代码 t100 s100 java

class Solution {
    public int getMinSwaps(String num, int k) {
        int len = num.length();
        int[] origin = new int[len];
        int[] temp = new int[len];
        for(int i=0; i<len; i++){
            origin[i] = num.charAt(i) - ‘0‘;
            temp[i] = origin[i];
        }
        while(k>0){
            temp = nextPermutation(temp);  
            k--;
        }
        int res = 0;
        for(int i=0; i<len; i++){
            if(origin[i]!=temp[i]){
                for(int j=i+1; j<len; j++){
                    if(origin[j]==temp[i]){
                        for(int h=j; h>i; h--){
                            myswap(origin, h, h-1);
                            res++;
                        }
                        break;
                    }
                }
            }
        }
        return res;
    }

    public int[] nextPermutation(int[] nums) {
        int len = nums.length;
        for(int i=len-1; i>0; i--){
            if(nums[i-1]<nums[i]){
                int j=i;
                for(; j<len; j++){
                    if(nums[j]<=nums[i-1]) break;
                }
                myswap(nums, i-1, j-1);
                int left = i, right = len-1;
                while(left<right){
                    myswap(nums, left++, right--);
                }
                return nums;                
            }
        }
        for(int i=0; i<len/2; i++){
            myswap(nums, i, len-1-i);
        }
        return nums;
    }

    public void myswap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

参考资料：
https://leetcode-cn.com/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/solution/lin-wei-jiao-huan-de-zui-xiao-ci-shu-by-xerp9/

5749. 邻位交换的最小次数

原文：https://www.cnblogs.com/zhengxch/p/14726684.html