1850. 邻位交换的最小次数

1850. 邻位交换的最小次数

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

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

• 例如，num = "5489355142" ：
  • 第 1 个最小妙数是 "5489355214"
  • 第 2 个最小妙数是 "5489355241"
  • 第 3 个最小妙数是 "5489355412"
  • 第 4 个最小妙数是 "5489355421"

返回要得到第 k 个 最小妙数 需要对 num 执行的 相邻位数字交换的最小次数 。

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

思路：首先求出第k个妙数，然后再计算移动的次数。

一、求下一个妙数（妙啊）

//求下一个妙数
public int[] miao(int[] nums){int len = nums.length;for(int i=len-1;i>=0;i--){if(nums[i] > nums[i-1]){int j = len - 1;while(nums[j] <= nums[i-1])   { j--; }//从i到j都比nums[i-1]大//nums[i-1]和nums[j]先调换位置swap(nums, i-1, j);//反转nums[i-1]之后的所有元素j = len - 1;while(i<j){swap(nums, i++, j--);}break;}}return nums;
}//交换nums数组第i和第j处的元素
public void swap(int[] nums, int i, int j){int m = nums[i];nums[i] = nums[j];nums[j] = m;
}

二、计算移动次数

class Solution {int res = 0;public int getMinSwaps(String num, int k) {int len = num.length();int[] nums = new int[len];int[] nums_k = new int[len];for(int i=0;i<len;i++){nums[i] = num.charAt(i) - '0';nums_k[i] = num.charAt(i) - '0';}for(int i=0;i<k;i++){nums_k = miao(nums_k);  //第k个妙数}for(int i=0;i<len;i++){if(nums[i] != nums_k[i]){int j = i+1;while(nums[j] != nums_k[i])  { j++; }  //找到相同数据，开始交换while(j != i){swap(nums, j-1, j);res++;j--;}}}return res;}
}

先码起来，这思路太强了，我就是个小菜鸡