Solutions CS101

Appearance

M3551.数位和排序需要的最小交换次数 ​

https://leetcode.cn/problems/minimum-swaps-to-sort-by-digit-sum/

给你一个由 互不相同 的正整数组成的数组 nums，需要根据每个数字的数位和（即每一位数字相加求和）按 升序 对数组进行排序。如果两个数字的数位和相等，则较小的数字排在前面。

返回将 nums 排列为上述排序顺序所需的 最小 交换次数。

一次 交换 定义为交换数组中两个不同位置的值。

示例 1：

输入: nums = [37,100]

输出: 1

解释:

  • 计算每个整数的数位和：[3 + 7 = 10, 1 + 0 + 0 = 1] → [10, 1]
  • 根据数位和排序：[100, 37]。将 37 与 100 交换，得到排序后的数组。
  • 因此，将 nums 排列为排序顺序所需的最小交换次数为 1。

示例 2：

输入: nums = [22,14,33,7]

输出: 0

解释:

  • 计算每个整数的数位和：[2 + 2 = 4, 1 + 4 = 5, 3 + 3 = 6, 7 = 7] → [4, 5, 6, 7]
  • 根据数位和排序：[22, 14, 33, 7]。数组已经是排序好的。
  • 因此，将 nums 排列为排序顺序所需的最小交换次数为 0。

示例 3：

输入: nums = [18,43,34,16]

输出: 2

解释:

  • 计算每个整数的数位和：[1 + 8 = 9, 4 + 3 = 7, 3 + 4 = 7, 1 + 6 = 7] → [9, 7, 7, 7]
  • 根据数位和排序：[16, 34, 43, 18]。将 18 与 16 交换，再将 43 与 34 交换，得到排序后的数组。
  • 因此，将 nums 排列为排序顺序所需的最小交换次数为 2。

提示:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • nums 由 互不相同 的正整数组成。

下面是一种基于「最小交换次数排序」的经典做法：

python
class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n = len(nums)
        # 1. 构造 (原下标, 值, 数位和) 三元组列表
        def digit_sum(x: int) -> int:
            s = 0
            while x:
                s += x % 10
                x //= 10
            return s

        arr = [(i, nums[i], digit_sum(nums[i])) for i in range(n)]
        
        # 2. 根据 (数位和, 值) 排序，得到目标位置
        arr_sorted = sorted(arr, key=lambda x: (x[2], x[1]))
        
        # 3. to[i] = 元素原来在 i，排序后应该去的位置
        to = [0] * n
        for new_pos, (orig_pos, _, _) in enumerate(arr_sorted):
            to[orig_pos] = new_pos
        
        # 4. 统计最小交换次数 = 所有环的 (环长 - 1) 之和
        visited = [False] * n
        swaps = 0
        for i in range(n):
            if visited[i] or to[i] == i:
                continue
            cycle_len = 0
            j = i
            while not visited[j]:
                visited[j] = True
                j = to[j]
                cycle_len += 1
            swaps += cycle_len - 1
        return swaps

思路解析

  1. 计算数位和：用一个 digit_sum 函数对每个 nums[i] 求各位数字之和。
  2. 确定目标顺序：将 (原下标, 值, 数位和) 三元组按 (数位和升序, 值升序) 排序，得到每个元素在排序后的目标下标。
  3. 建立映射：用数组 to 表示当前位置到目标位置的映射：to[orig_pos] = new_pos。
  4. 最小交换次数 = 排序映射的最小换位
    • 这相当于给定一个长度为 n 的排列，用最少的两两交换将其变成恒等排列。
    • 每个环（cycle）长为 k 都需要 k-1 次交换。
    • 因此遍历一遍、把所有环长度累加 (k-1)，就是答案。

该算法的总体时间复杂度为 O(nlog⁡n)，满足 n≤105 的要求。