题解 | #数组中的逆序对#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param data int整型一维数组 
 * @return int整型
*/
/*
*
本质上利用归并排序，实现分治
【关键】通过归并，统计左半边数组元素 > 右半边数组元素的的个数
*/
var (
	res  = 0
	base = 1000000007
)
func InversePairs( data []int ) int {
    // write code here
    arr := data
	if len(arr) == 0 {
		return res
	}
	sort(arr, 0, len(arr)-1)
	return res
}

func sort(arr []int, left, right int) {
	if left >= right {
		return
	}
	mid := left + (right-left)/2
	sort(arr, left, mid)
	sort(arr, mid+1, right)
	merge(arr, left, mid, right)
}

func merge(arr []int, left, mid, right int) {
	tmp := make([]int, 0)
	lIndex := left
	rIndex := mid + 1
	//统计左右边大小: 从小到大
	for lIndex <= mid && rIndex <= right {
		if arr[rIndex] < arr[lIndex] {
			tmp = append(tmp, arr[rIndex])
			rIndex++
			//【关键】通过归并，统计左半边数组元素 > 右半边数组元素的的个数
			res += mid - lIndex + 1
			res %= base
		} else {
			tmp = append(tmp, arr[lIndex])
			lIndex++
		}
	}
	//将剩余的加到后面
	for ; lIndex <= mid; lIndex++ {
		tmp = append(tmp, arr[lIndex])
	}
	for ; rIndex <= right; rIndex++ {
		tmp = append(tmp, arr[rIndex])
	}
	//将数据放回原来的位置
	for i := 0; i < len(tmp); i++ {
		arr[left] = tmp[i]
		left++
	}
}