面试题-最小交换次数（可以交换任意两个位置的元素）

Categories:

题目描述
思路分析
1. 解法一：置换环分解（推荐）
相似题目

题目描述

✅ 面试题：最小交换次数（可以交换任意两个位置的元素）

给定一个无序整数数组 nums，你可以交换数组中任意两个位置的元素，求使数组变为递增序列的最小交换次数。

思路分析

解法一：置换环分解（推荐）

核心思路：

将数组元素与原下标组成二元组，按值升序（值相同按原下标升序）排序。

排序后第 i 位应当放置原下标为 pairs[i].index 的元素。

该映射形成置换，最小交换次数等于所有环的 (长度 - 1) 之和。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于辅助数组与访问标记。

class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;
        int[][] pairs = new int[n][2];

        for (int i = 0; i < n; i++) {
            pairs[i][0] = nums[i];
            pairs[i][1] = i;
        }

        Arrays.sort(pairs, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return a[1] - b[1];
        });

        boolean[] visited = new boolean[n];
        int swaps = 0;

        for (int i = 0; i < n; i++) {
            if (visited[i] || pairs[i][1] == i) {
                continue;
            }

            int cycle = 0;
            int cur = i;
            while (!visited[cur]) {
                visited[cur] = true;
                cur = pairs[cur][1];
                cycle++;
            }

            swaps += cycle - 1;
        }

        return swaps;
    }
}

import "sort"

func minSwaps(nums []int) int {
	n := len(nums)
	pairs := make([][2]int, n)
	for i := 0; i < n; i++ {
		pairs[i] = [2]int{nums[i], i}
	}

	sort.Slice(pairs, func(i, j int) bool {
		if pairs[i][0] != pairs[j][0] {
			return pairs[i][0] < pairs[j][0]
		}
		return pairs[i][1] < pairs[j][1]
	})

	visited := make([]bool, n)
	swaps := 0

	for i := 0; i < n; i++ {
		if visited[i] || pairs[i][1] == i {
			continue
		}

		cycle := 0
		cur := i
		for !visited[cur] {
			visited[cur] = true
			cur = pairs[cur][1]
			cycle++
		}

		swaps += cycle - 1
	}

	return swaps
}

相似题目

题目	难度	考察点
765. 情侣牵手	困难	最少交换
1202. 交换字符串中的元素	中等	并查集
41. 缺失的第一个正数	困难	原地置换
448. 找到所有数组中消失的数字	简单	原地标记
287. 寻找重复数	中等	环检测

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/58275608