题目链接3551. 数位和排序需要的最小交换次数中等算法原理解法迭代计算285ms击败80.81%时间复杂度O(n logn)①预处理遍历数组记录每个数字的数位和、数字本身、原本数组下标②排序按照数位和升序数位相同则数值升序排序得到目标序列③置换环统计利用保存的原始下标找到所有置换环包括自环统计置换环总数 cc原理长度为 k 的环需要 k-1 次交换比如自环就需要 0 次交换~~Java代码class Solution { //3551. 数位和排序需要的最小交换次数 public int minSwaps(int[] nums) { int nnums.length; int[][] anew int[n][3]; //计算每个数字的数位和保存原值、原始下标 for(int i0;in;i){ int s0; for(int xnums[i];x0;x/10) sx%10; a[i][0]s; a[i][1]nums[i]; a[i][2]i; } //数位和升序数位和相同则按数值升序 Arrays.sort(a,(p,q)-p[0]!q[0]?p[0]-q[0]:p[1]-q[1]); int cc0;//置换环总个数包括自环 //遍历寻找所有置换环 for(int[] t:a){ int it[2];//取出原始下标 if(i0) continue;//-1标记已访问跳过 cc;//找到一个全新的环 while(i0){ int nxta[i][2];//当前位置指向环的下一个位置 a[i][2]-1;//防止重复处理 inxt;//跳到环的下一个节点继续循环 } } //最小交换次数总元素个数置换环总数量包括自环 return n-cc; } }