• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

5749. 邻位交换的最小次数

开发技术 开发技术 1周前 (05-02) 4次浏览

难度 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. 邻位交换的最小次数
喜欢 (0)