力扣 LeetCode 3551. 数位和排序需要的最小交换次数 - 力扣（LeetCode） 3551. 数位和排序需要的最小交换次数 - 给你一个由 互不相同 的正整数组成的数组 nums，需要根据每个数字的数位和（即每一位数字相加求和）按 升序 对数组进行排序。如果两个数字的数位和相等，则较小的数字排在前面。 返回将 nums 排列为上述排序顺序所需的 最小 交换次数。 一次 交换 定义为交换数组中两个不同位置的值。   示例 1： 输入: nums = [37,100] 输出: 1 解释: * 计算每个整数的数位和：[3 + 7 = 10, 1 + 0 + 0 =... 思路 首先是排序，因为要用到数位和、原数和下标，所以要把这三个信息都存起来。 然后是交换，不在正确位置的数都能形成环(a->b->c->a)。只要不故意多交换，那交换次数就是一定的。但是我们要实时更新另一个数(还没遇到的那个)交换后的位置，所以要用Map存起来。 代码 class Solution { public int minSwaps(int[] nums) { int n = nums.length; HashMap<Integer, int[]> map = new HashMap<>(); int[][] sorted = new int[n][3]; for (int i = 0; i < n; i++) { int sum = 0; for (int x = nums[i]; x > 0; x /= 10) { sum += x % 10; } sorted[i][0] = sum; sorted[i][1] = nums[i]; sorted[i][2] = i; map.put(nums[i], sorted[i]); } Arrays.sort(sorted, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]); int ans = 0; for (int i = 0; i < n; i++) { int idx = sorted[i][2]; if (idx != i) { ans++; int[] tmp = map.get(nums[i]); tmp[2] = idx; nums[idx] = nums[i]; } } return ans; } } 1 个帖子 - 1 位参与者 阅读完整话题

  • 情报分类：综合情报
  • 分类依据：内容未命中明确的垂直分类规则，归入综合情报
  • 信息来源：服务器 / LINUX DO - 最新话题
  • 发布时间：2026/10/17 09:26:51