2025-11-04：数位和排序需要的最小交换次数。用go语言，给定一个由不同的正整数构成的数组 nums，要求按照每个数各位数字之和从小到大重新排列数组；当两数的各位和相同时，数值更小的排在前面。问要把 nums 调整到这种顺序，至少需要进行多少次交换操作？这里一次交换指把数组中两个不同索引位置上的元素互换。

1 <= nums.length <= 100000。

1 <= nums[i] <= 1000000000。

nums 由 互不相同 的正整数组成。

输入: 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。

题目来自力扣3551。

算法步骤详细描述

第一步：计算数位和并构建元组数组

1. 对于数组中的每个数字，计算其各位数字之和
   • 例如：18 → 1+8=9，43 → 4+3=7，34 → 3+4=7，16 → 1+6=7
2. 为每个数字创建一个三元组（数位和，数字本身，原始索引）
   • 这样我们就得到了一个包含额外信息的数组

第二步：按规则排序

1. 对三元组数组进行排序，主要排序规则：
   • 首先按数位和从小到大排序
   • 当数位和相同时，按数字本身从小到大排序
2. 排序后得到目标顺序：16(7), 34(7), 43(7), 18(9)

第三步：检测循环节（关键步骤）

1. 遍历排序后的数组，对于每个元素：
   • 如果该元素的原始索引未被访问过（标记为负数表示已访问）
   • 开始一个新的循环节计数
2. 对于每个新发现的循环节：
   • 从当前元素的原始索引开始，沿着索引链追踪
   • 将访问过的索引标记为已访问（设为负数）
   • 直到回到起点或遇到已访问的索引

第四步：计算最小交换次数

• 最小交换次数 = 数组长度 - 循环节数量
• 原理：每个长度为k的循环节需要k-1次交换才能归位
• 总交换次数 = Σ(每个循环节长度-1) = 总元素数 - 循环节数

示例分析

对于输入 [18, 43, 34, 16]：

• 排序后目标顺序：16, 34, 43, 18
• 检测到2个循环节：
  • 循环节1：位置0↔3（元素16和18）
  • 循环节2：位置1↔2（元素34和43）
• 最小交换次数 = 4 - 2 = 2

复杂度分析

总的时间复杂度：O(n log n)

• 计算数位和：O(n × d)，其中d是数字的最大位数（本题d≤10，可视为常数）
• 排序：O(n log n)
• 循环节检测：O(n)
• 主导项：O(n log n)

总的额外空间复杂度：O(n)

• 存储三元组数组：O(n)
• 无其他显著空间开销

该算法通过巧妙的循环节检测，将最小交换次数问题转化为图论中的循环节计数问题，实现了高效求解。

Go完整代码如下：

package main

import (
	"cmp"
	"fmt"
	"slices"
)

func minSwaps(nums []int) int {
	n := len(nums)
	type tuple struct{ s, x, i int }
	a := make([]tuple, n)
	for i, num := range nums {
		s := 0
		for x := num; x > 0; x /= 10 {
			s += x % 10
		}
		a[i] = tuple{s, num, i}
	}

	slices.SortFunc(a, func(a, b tuple) int { return cmp.Or(a.s-b.s, a.x-b.x) })

	cc := 0
	for _, p := range a {
		if p.i < 0 { // 访问过
			continue
		}
		cc++
		for i := p.i; i >= 0; {
			i, a[i].i = a[i].i, -1
		}
	}
	return n - cc
}

func main() {
	nums := []int{18, 43, 34, 16}
	result := minSwaps(nums)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def min_swaps(nums):
    n = len(nums)
    # 创建元组列表 (数位和, 数字, 原索引)
    arr = []
    for i, num in enumerate(nums):
        digit_sum = 0
        temp = num
        while temp > 0:
            digit_sum += temp % 10
            temp //= 10
        arr.append((digit_sum, num, i))
    
    # 排序：先按数位和，再按数字本身
    arr.sort(key=lambda x: (x[0], x[1]))
    
    # 计算循环节数量
    visited = [False] * n
    cycle_count = 0
    
    for i in range(n):
        if not visited[i]:
            cycle_count += 1
            j = i
            while not visited[j]:
                visited[j] = True
                j = arr[j][2]  # 获取原索引
    
    return n - cycle_count

def main():
    nums = [18, 43, 34, 16]
    result = min_swaps(nums)
    print(result)

if __name__ == "__main__":
    main()