数组中的逆序对

1. 题目描述

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

2. 思路

• 暴力法
• 归并排序法
  • 归并的时候，如果是右边的数归并上去，那么说明左边的数>右边的数，这个区间就是逆序对
  • 

3. 实现

3.1. 暴力法

//时间复杂度：O(N^2)
//空间复杂度：O(1)
func InversePairs(data []int) int {
	count := 0
	for i := 0; i < len(data); i++ {
		for j := i + 1; j < len(data); j++ {
			if data[i] > data[j] {
				count++
			}
		}
	}
	return count % 1000000007
}

3.2. 归并排序法

//时间复杂度：O(NlogN)
//空间复杂度：O(N)
func reversePairs(nums []int) int {
	ret := 0
	mergeSort(nums, 0, len(nums)-1, &ret)
	return ret
}


func mergeSort(data []int, left int, right int, ret *int) {
	if left >= right {
		return
	}
 
	mid := left + (right-left)>>1
	mergeSort(data, left, mid, ret)
	mergeSort(data, mid+1, right, ret)
 
	//有序数组那么没必要调用merge
	if data[mid] > data[mid+1] {
		merge(data, left, mid, right, ret)
	}
 
}
 
func merge(data []int, left int, mid int, right int, ret *int) {
	length := right - left + 1
	tmp := make([]int, length)
	i := left
	j := mid + 1
	k := 0
	for i <= mid && j <= right {
        // 严格大于
		if data[i] > data[j] {
			tmp[k] = data[j]
			k++
			j++
 
			*ret = (*ret + (mid - i + 1)) % 1000000007
		} else {
			tmp[k] = data[i]
			k++
			i++
		}
	}
 
	for i <= mid {
		tmp[k] = data[i]
		k++
		i++
	}
	for j <= right {
		tmp[k] = data[j]
		k++
		j++
	}
 
	k = 0
	i = left
	for i <= right {
		data[i] = tmp[k]
		i++
		k++
	}
}
 

4. 参考

• 数组中的逆序对_牛客网
• 剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode）