题意

逆序对,如果前面的元素大于后面的元素则为一个逆序对,统计一个数组中逆序对的个数并返回

思路

思路:每次遇到左半边数组的元素大于右边数组元素,说明产生逆序对

产生逆序对的个数为:(mid - 左边数组元素当前下标 + 1)。说明有这么多个元素是大于当前右边数组这个元素。

一句话总结就是:如果右半部分数组当前元素小于左半部分数组的当前元素,那么当前左半部分数组的当前元素后面的元素(包括当前元素)都是大于右半部分数组当前元素的,也就是统计左半部分数组当前元素后面元素(包括当前元素)有多少个即可。

例如:左半部分数组为1,3,4 右半部分数组为1,2,5
那么如果当前左半部分数组元素为3,右半部分数组当前元素为2,此时产生的逆序对便是左半部分数组元素3右边所有的元素(包括3这个元素)

具体实现

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
52
53
54
55
56
57
58
59
60
61
func MergeSort(nums []int) int {
if nums == nil || len(nums) < 2 {
return 0
}
return mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, l, r int) int {
//递归结束条件
if l == r {
return 0
}

//注意这个写法:可以避免越界同时使用>>1加速运算
mid := l + (r-l)>>1
//分治
return mergeSort(nums, l, mid) + mergeSort(nums, mid+1, r) + merge(nums, l, mid, r)

//合并两部分[l,mid] [mid+1,r]
}

func merge(nums []int, l, mid, r int) int {
i, j := l, mid+1
//申请一个辅助数组
help := make([]int, r-l+1)
index := 0
ret := 0
//谁小填谁移谁
for i <= mid && j <= r {
if nums[i] > nums[j] { //产生逆序对
help[index] = nums[j]
ret += (mid - i + 1)
j++
} else {
help[index] = nums[i]
i++
}
index++
}

//移动剩下的一部分
//注意下面两个是for循环,不是if
//另外注意的是下面两个for循环有且只有一个可以被执行
for i <= mid {
help[index] = nums[i]
index++
i++
}

for j <= r {
help[index] = nums[j]
index++
j++
}

//此时help已经填充好我们排序后的数字了,我们需要将且拷贝到原数组的l->r
for i := l; i <= r; i++ {
nums[i] = help[i-l]
}
return ret
}

评论