数组中的逆序对

发表于

描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007

数据范围：

  • 对于50%的数据， size≤104
  • 对于100%的数据， size≤105
  • 数组中所有数字的值满足 0≤|val|≤109

要求： 空间复杂度O(n)，时间复杂度O(nlogn)

输入描述
题目保证输入的数组中没有的相同的数字

示例1

1
2
输入:  [1,2,3,4,5,6,7,0]
返回:  7

示例2

1
2
输入:  [1,2,3]
返回:  0

题解

归并排序、递归

先分: 将数组分为两个子数组，两个子数组分为四个子数组，依次向下分，直到数组不能再分为止
合并: 就是从最小的数组按照顺序合并，从小到大或从大到小，依次向上合并，最后得到合并完的顺序数组

Tips: 在合并数组的时候，当发现右边的小于左边的时候，此时可以直接求出当前产生的逆序对的个数

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
62
63
64
65
66
67
68
69
70
package main

/**
 *
 * @param data int整型一维数组
 * @return int整型
 */

func InversePairs(data []int) int {
	// write code here
	tmp := make([]int, len(data))
	count := 0
	mergeSort(data, tmp, 0, len(data)-1, &count)
	return count
}

func mergeSort(data, tmp []int, start, end int, count *int) {
	if start >= end {
		return
	}

	mid := start + (end-start)>>1

	mergeSort(data, tmp, start, mid, count)
	mergeSort(data, tmp, mid+1, end, count)
	merge(data, tmp, start, mid, end, count)

	return

}

func merge(data, tmp []int, start, mid, end int, count *int) {
	if start >= end {
		return
	}

	i := start
	j := mid + 1
	k := start
	for i <= mid && j <= end {
		if data[i] <= data[j] {
			tmp[k] = data[i]
			i++
		} else {
			*count = *count + (mid - i + 1)
			*count = *count % 1000000007
			tmp[k] = data[j]
			j++
		}
		k++
	}

	for i <= mid {
		tmp[k] = data[i]
		i++
		k++
	}

	for j <= end {
		tmp[k] = data[j]
		j++
		k++
	}

	for i = start; i <= end; i++ {
		data[i] = tmp[i]
	}

	return
}