LeetCode 补充题 101. 数组排序的最少交换次数
题目描述
给你一个元素互不相同的整数数组
nums，请分别求出在以下两种交换规则下，将数组按递增顺序排列所需的最少交换次数：
- 任意交换： 每次可以交换任意两个位置的元素。
- 相邻交换： 每次只能交换相邻两个位置的元素。
两种规则分别计算，不能在同一次排序过程中混用。
示例 1：
输入：
nums = [4,3,2,1]
输出： 任意交换为2，相邻交换为6。
解释： 任意交换时，分别交换4与1、3与2即可完成排序；只允许相邻交换时，最少需要6次。
示例 2：
输入：
nums = [1,2,3]
输出： 任意交换为0，相邻交换为0。
解释： 数组已经按递增顺序排列，无需交换。
提示：
-
nums中的元素均为整数，且互不相同。 - 两种交换规则分别计算最少次数。
题意分析
两种规则只差“相邻”两个字，解法却完全不同：
- 任意交换：将位置关系拆成置换环。长度为
L的环需要L - 1次交换。- 相邻交换：每次交换至多消除一个逆序对，答案就是逆序对数。
本题按元素互不相同处理。如果允许重复元素，相邻交换的结论仍然成立，但任意交换时，相同值可能对应多个目标位置，随意固定映射后统计环长不一定得到最少次数，不能直接套用本解。
解法一：任意交换——置换环
核心思路
[!blue]
将下标按元素值排序。排序后
idx[i]表示：最终位于位置i的元素，当前在位置idx[i]。它记录的是“目标位置 → 原位置”，与“原位置 → 目标位置”互为逆映射；两者的环方向相反，但环内位置及环长相同，因此沿j = idx[j]遍历即可。元素互不相同，因此每个位置都有唯一来源，整个映射可拆为互不相交的环。交换同一环中的两个位置会把它拆成两个环，交换不同环中的位置则会把两环合并，所以一次交换最多让环数增加 1。若最初有
c个环，排好序时必须有n个单点环，至少需要n - c次交换；跨环交换也无法突破这个下界。在同一个环内反复把一个元素交换到目标位置，每次都能拆出一个单点环，最后剩下的元素自动归位。长度为
L的环恰好用L - 1次，各环相加就是n - c，达到上述下界。因此只需沿idx统计各环长度并累加size - 1，不用实际交换输入。
visited防止同一个环被重复计算。长度为 1 的环表示已经归位，贡献为 0；空数组也自然返回 0。
解题步骤
- 创建下标数组
idx = [0, 1, ..., n - 1]，按对应元素值升序排序。- 使用
visited标记已访问位置。- 从每个未访问位置出发，沿
idx统计环长size。- 每个环对答案贡献
size - 1。
代码实现
class Solution {
public int minSwaps(int[] nums) {
int n = nums.length;
Integer[] idx = new Integer[n];
for (int i = 0; i < n; i++) {
idx[i] = i;
}
Arrays.sort(idx, (a, b) -> Integer.compare(nums[a], nums[b]));
boolean[] visited = new boolean[n];
int swaps = 0;
for (int i = 0; i < n; i++) {
if (visited[i] || idx[i] == i) {
continue;
}
int size = 0;
for (int j = i; !visited[j]; j = idx[j]) {
visited[j] = true;
size++;
}
swaps += size - 1;
}
return swaps;
}
}
import (
"sort"
)
func minSwaps(nums []int) int {
idx := make([]int, len(nums))
for i := range idx {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool {
return nums[idx[i]] < nums[idx[j]]
})
visited := make([]bool, len(nums))
swaps := 0
for i := range idx {
if visited[i] || idx[i] == i {
continue
}
size := 0
for j := i; !visited[j]; j = idx[j] {
visited[j] = true
size++
}
swaps += size - 1
}
return swaps
}
复杂度分析
- 时间复杂度：$O(n \log n)$。下标排序需要 $O(n \log n)$，遍历全部置换环共需 $O(n)$，因为每个位置至多访问一次。
- 空间复杂度：$O(n)$，用于下标数组、访问标记及排序辅助空间。
关键点总结
[!green]
- 长度为
L的置换环最少需要L - 1次交换。- 已经归位的元素是长度为 1 的环，贡献 0。
- 如果数组本身是
0..n-1的排列，可以省去排序，时间降为 $O(n)$。
解法二：相邻交换——逆序对
核心思路
[!blue]
逆序对是满足
i < j且nums[i] > nums[j]的下标对。排序完成时逆序对数为 0，而交换相邻元素只改变这两个元素之间的前后关系，它们与其他元素的相对顺序保持不变。因此一次交换最多消除一个逆序对，原有逆序对数就是所需次数的下界。只要数组尚未递增，就至少存在一对相邻的逆序元素。每次交换这样的一对，逆序对数恰好减少 1；一直重复到逆序对数为 0，就能达到这个下界。因此最少相邻交换次数等于逆序对数，无需实际模拟全部交换。
用归并排序统计时，
mergeCount(arr, tmp, left, right)负责把当前区间排序，并返回排序前该区间内的逆序对数。先递归统计左右两半内部的逆序对，再在合并阶段统计左端点在左半区、右端点在右半区的逆序对，三部分互不重复。合并时，若
arr[i] <= arr[j]，左侧当前值不大于右侧任何剩余值，取出它不会增加跨区间计数。否则左侧从i到mid的所有剩余值都大于arr[j]，一次累加mid - i + 1，再取出右侧当前值。合并结果写回arr后，上层递归才能继续利用区间有序的性质。区间长度不超过 1 时返回 0，空数组也由这一条件处理。代码先复制输入，归并只修改副本；逆序对总数可能超过 32 位整数范围，因此返回值和累计变量都使用 64 位整数。
解题步骤
- 复制输入数组，并分配可复用的归并缓冲区
tmp。- 当前区间长度不超过 1 时返回 0，否则递归排序左右两半，并累加各自内部的逆序对数。
- 合并时，左值不大于右值就先取左值；右值更小时累加
mid - i + 1，再取右值。- 补齐未取完的元素，将缓冲区的当前区间写回
arr，返回本区间的 64 位计数。
代码实现
class Solution {
public long minSwaps(int[] nums) {
int[] arr = nums.clone();
return mergeCount(arr, new int[arr.length], 0, arr.length - 1);
}
private long mergeCount(int[] arr, int[] tmp, int left, int right) {
if (left >= right) {
return 0L;
}
int mid = left + (right - left) / 2;
long count = mergeCount(arr, tmp, left, mid) + mergeCount(arr, tmp, mid + 1, right);
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
tmp[k++] = arr[i++];
} else {
count += mid - i + 1;
tmp[k++] = arr[j++];
}
}
while (i <= mid) {
tmp[k++] = arr[i++];
}
while (j <= right) {
tmp[k++] = arr[j++];
}
System.arraycopy(tmp, left, arr, left, right - left + 1);
return count;
}
}
func minSwaps(nums []int) int64 {
arr := append([]int(nil), nums...)
tmp := make([]int, len(arr))
return mergeCount(arr, tmp, 0, len(arr)-1)
}
func mergeCount(arr, tmp []int, left, right int) int64 {
if left >= right {
return 0
}
mid := left + (right-left)/2
count := mergeCount(arr, tmp, left, mid) + mergeCount(arr, tmp, mid+1, right)
i, j, k := left, mid+1, left
for i <= mid && j <= right {
if arr[i] <= arr[j] {
tmp[k] = arr[i]
i++
} else {
count += int64(mid - i + 1)
tmp[k] = arr[j]
j++
}
k++
}
for i <= mid {
tmp[k] = arr[i]
i++
k++
}
for j <= right {
tmp[k] = arr[j]
j++
k++
}
copy(arr[left:right+1], tmp[left:right+1])
return count
}
复杂度分析
- 时间复杂度：$O(n \log n)$。归并递归共 $O(\log n)$ 层，每层处理的元素总数为 $O(n)$。
- 空间复杂度：$O(n)$。输入副本和归并缓冲区各占 $O(n)$，递归栈另占 $O(\log n)$。
关键点总结
[!green]
- 最小相邻交换次数等于逆序对数。
mid - i + 1是归并阶段批量统计逆序对的关键。- 相等元素不构成逆序对，合并时要使用
arr[i] <= arr[j]。- 逆序对最多有 $\frac{n(n-1)}{2}$ 个，计数结果要用 64 位整数。
易错点总结
[!yellow]
- 不确认交换规则，直接套错模型。
- 任意交换时忘记元素互不相同的前提。
- 相邻交换用冒泡排序模拟，结果正确，但时间复杂度为 $O(n^2)$。
- 归并时把相等元素误算成逆序对。
- 使用
int保存逆序对数，数组较长时可能溢出。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 765. 情侣牵手 | 困难 | 同样通过交换拆解置换关系，本题元素目标位置固定，原题还要先把情侣关系映射为连通分量。 |
| 剑指 Offer 51. 数组中的逆序对 | 困难 | 相邻交换次数由逆序对计数，不能用任意交换的置换环答案替代。 |