小米面试题-最小交换次数（只能交换相邻位置的元素）

题目描述

✅ 小米面试题-最小交换次数（只能交换相邻位置的元素）

给定一个无序整数数组 nums，你只能交换相邻的元素，求将数组排序成递增顺序所需的最小交换次数。

思路分析

思路描述

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51



func minSwaps(nums []int) int {
	if len(nums) <= 1 {
		return 0
	}

	var merge func(nums []int, left, right int) int
	merge = func(nums []int, left, right int) int {
		if left >= right {
			return 0
		}

		mid := left + (right-left)/2

		count := merge(nums, left, mid) + merge(nums, mid+1, right)

		i, j := left, mid+1
		k := 0
		res := make([]int, right-left+1)
		for i <= mid && j <= right {
			if nums[i] <= nums[j] {
				res[k] = nums[i]
				i++
			} else {
				res[k] = nums[j]
				j++
				count += mid - i + 1
			}
			k++
		}

		for i <= mid {
			res[k] = nums[i]
			i++
			k++
		}
		for j <= right {
			res[k] = nums[j]
			j++
			k++
		}

		for p := 0; p < len(res); p++ {
			nums[left+p] = res[p]
		}

		return count
	}

	res := merge(nums, 0, len(nums)-1)
	return res
}





1



write your code here

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2025/42340608
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！