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

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型
 */
func InversePairs(nums []int) int {
	var mergeSort func (nums []int) int
	mergeSort = func(nums []int) int {
		if len(nums) < 2 {
			return 0
		}
		mid := len(nums)/2
		leftNums := make([]int,mid)
		rightNums := make([]int,len(nums)-mid)
		copy(leftNums, nums[:mid])
		copy(rightNums, nums[mid:])

		leftCount := mergeSort(leftNums)
		rightCount := mergeSort(rightNums)
		i, j := 0, 0
		mergeCount := 0
		for k := 0;k < len(nums); k++ {
			if i < len(leftNums) && (j >= len(rightNums) || leftNums[i] <= rightNums[j]){
				// 直接使用nums记录省去拷贝的时间
				nums[k] = leftNums[i]
				i++
			}else{
				nums[k] = rightNums[j]
				j++
				mergeCount += len(leftNums) - i
			}
		}		
		return leftCount + rightCount + mergeCount
	}
	return mergeSort(nums) % 1000000007
}