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

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型
 */

var count = 0
const kmod = 1000000007
func InversePairs(nums []int) int {
	MergeSort(nums)
	return count
}

func MergeSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	mid := len(arr) / 2
	left := MergeSort(arr[:mid])
	right := MergeSort(arr[mid:])

	return merge(left, right)
}

func merge(left, right []int) []int {
	res := make([]int, 0, len(right)+len(left))
	i, j := 0, 0

	for i < len(left) && j < len(right) {
		if left[i] < right[j] {
			res = append(res, left[i])
			i++
		} else {
			res = append(res, right[j])
		  	// 关键步骤，存在逆序的时候，记录逆序
			count += len(left) - i
            count %= kmod
			j++
		}
	}
	res = append(res, left[i:]...)
	res = append(res, right[j:]...)
	return res
}