面试题-最小交换次数（可以交换任意两个位置的元素）
题目描述
✅ 面试题：最小交换次数（可以交换任意两个位置的元素）
给定一个无序整数数组 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
func minSwaps(nums []int) int {
n := len(nums)
var sortedNums = make([]int, n)
copy(sortedNums, nums)
sort.Ints(sortedNums)
// 记录每个元素在排序后的数组中的位置
pos := make(map[int]int)
for i, num := range sortedNums {
pos[num] = i
}
// 用一个数组记录元素是否已经访问过
visited := make([]bool, n)
swaps := 0
for i := 0; i < n; i++ {
// 如果元素已经访问过，或者已经在正确位置，跳过
if visited[i] || pos[nums[i]] == i {
continue
}
// 计算环的大小
cycleSize := 0
cur := i
for !visited[cur] {
visited[cur] = true
next := pos[nums[cur]]
cur = next
cycleSize++
}
// 如果环的大小大于 1，最小交换次数是环大小减去 1
if cycleSize > 1 {
swaps += cycleSize - 1
}
}
return swaps
}
1
write your code here
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！