面试题-最小交换次数（任意交换与相邻交换）
目录
题目描述
给定一个元素互不相同的整数数组
nums，求将数组排成递增顺序所需的最小交换次数。面试时必须先确认交换规则：
- 可以交换任意两个位置的元素。
- 只能交换相邻位置的元素。
题意分析
两种规则只差“相邻”两个字，解法却完全不同：
- 任意交换：将位置关系拆成置换环。长度为
L的环需要L - 1次交换。- 相邻交换：每次交换只能消除一个逆序对，答案就是逆序对数。
例如
nums = [4, 3, 2, 1]：任意交换只需 2 次，相邻交换需要 6 次。本题按元素互不相同处理。如果允许重复元素，相邻交换的结论仍然成立，但任意交换时需要额外确定相同值与目标位置的映射。
解法一：任意交换——置换环
核心思路
将下标按元素值排序。排序后
idx[i]表示：最终位于位置i的元素，当前在位置idx[i]。这个映射会形成若干个置换环。对于长度为
L的环，每次把一个元素换到正确位置，恰好需要L - 1次。
解题步骤
- 创建下标数组
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;
}
}
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)$。
关键点总结
- 长度为
L的置换环最少需要L - 1次交换。- 已经归位的元素是长度为 1 的环，贡献 0。
- 如果数组本身是
0..n-1的排列，可以省去排序，时间降为 $O(n)$。
解法二：相邻交换——逆序对
核心思路
逆序对是满足
i < j且nums[i] > nums[j]的下标对。一次相邻交换只会改变这两个元素的前后关系，最多消除一个逆序对，所以至少需要“逆序对数”次交换。冒泡排序又能恰好用这么多次完成排序。
因此，最小相邻交换次数 = 逆序对数。用归并排序可在 $O(n \log n)$ 时间内统计。
解题步骤
- 递归排序左右两半，并统计各自内部的逆序对。
- 合并两个有序区间。
- 当
arr[i] > arr[j]时，左区间从i到mid的元素都与arr[j]构成逆序对，累加mid - i + 1。
代码实现
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, j = mid + 1, 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(n)$，递归栈为 $O(\log n)$。
关键点总结
- 最小相邻交换次数等于逆序对数。
mid - i + 1是归并阶段批量统计逆序对的关键。- 相等元素不构成逆序对，合并时要使用
arr[i] <= arr[j]。- 逆序对最多有 $\frac{n(n-1)}{2}$ 个，计数结果要用 64 位整数。
解法对比
| 交换规则 | 核心模型 | 答案 | 时间复杂度 |
|---|---|---|---|
| 任意两个位置 | 置换环 | 所有环的 size - 1 之和 |
$O(n \log n)$ |
| 只能交换相邻元素 | 逆序对 | 逆序对总数 | $O(n \log n)$ |
易错点总结
- 不确认交换规则，直接套错模型。
- 任意交换时忘记元素互不相同的前提。
- 相邻交换用冒泡排序模拟，结果正确，但时间复杂度为 $O(n^2)$。
- 归并时把相等元素误算成逆序对。
- 使用
int保存逆序对数，数组较长时可能溢出。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 315. 计算右侧小于当前元素的个数 | 困难 | 归并统计逆序对 |
| 493. 翻转对 | 困难 | 归并计数 |
| 765. 情侣牵手 | 困难 | 置换环 |
| 2471. 逐层排序二叉树所需的最少操作数 | 中等 | 置换环 |