LeetCode 题解工作台
数位和排序需要的最小交换次数
给你一个由 互不相同 的正整数组成的数组 nums ，需要根据每个数字的数位和（即每一位数字相加求和）按 升序 对数组进行排序。如果两个数字的数位和相等，则较小的数字排在前面。 返回将 nums 排列为上述排序顺序所需的 最小 交换次数。 一次 交换 定义为交换数组中两个不同位置的值。 示例 1： …
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
class Solution: def minSwaps(self, nums: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个由 互不相同 的正整数组成的数组 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 <= 1051 <= nums[i] <= 109nums由 互不相同 的正整数组成。
解题思路
方法一
class Solution:
def minSwaps(self, nums: List[int]) -> int:
def f(x: int) -> int:
s = 0
while x:
s += x % 10
x //= 10
return s
n = len(nums)
arr = sorted((f(x), x) for x in nums)
d = {a[1]: i for i, a in enumerate(arr)}
ans = n
vis = [False] * n
for i in range(n):
if not vis[i]:
ans -= 1
j = i
while not vis[j]:
vis[j] = True
j = d[nums[j]]
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n) for sorting plus O(n) for mapping and swap counting, yielding overall O(n log n). Space complexity is O(n) for storing digit sums and the index map, as each element needs position tracking. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate sorts based on a computed key and tiebreaker, checking digit sum logic.
- question_mark
Using a hash map to track original indices shows recognition of array scanning plus hash lookup.
- question_mark
Counting swaps via visited positions indicates understanding of minimal swap strategies.
常见陷阱
外企场景- error
Ignoring the numeric value tiebreaker when digit sums are equal, leading to wrong sort order.
- error
Failing to track visited indices, which can double-count swaps or cause infinite loops.
- error
Attempting swaps without mapping indices, resulting in inefficient O(n^2) operations.
进阶变体
外企场景- arrow_right_alt
Sort by sum of squares of digits instead of digit sum to test generalized key-based swaps.
- arrow_right_alt
Handle arrays with repeated numbers to test extensions beyond distinct values.
- arrow_right_alt
Compute maximum swaps allowed rather than minimum to explore constrained swap scenarios.