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

package main
// import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
*/
func InversePairs( nums []int ) int {
    // write code here
    var res int

    merge := func(nums []int, left, mid, right int) {
        tmpLeft := make([]int, 0, mid-left+1)
        tmpRight := make([]int, 0, right-mid)
        for i := left; i <= mid; i++ {
            tmpLeft = append(tmpLeft, nums[i])
        }
        for i := mid+1; i <= right; i++ {
            tmpRight = append(tmpRight, nums[i])
        }
        i, j, k := 0, 0, left
        for i < len(tmpLeft) && j < len(tmpRight) {
            if tmpLeft[i] <= tmpRight[j] {
                nums[k] = tmpLeft[i]
                i++
            } else {
                nums[k] = tmpRight[j]
                j++ 
                res = res+len(tmpLeft)-i
            }
            k++
        }
        for i < len(tmpLeft) {
            nums[k] = tmpLeft[i]
            i++
            k++
        }
        for j < len(tmpRight) {
            nums[k] = tmpRight[j]
            j++
            k++
        }
    }

    var sortMerge func([]int, int, int)
    sortMerge = func(nums []int, left, right int) {
        if left == right {
            return
        }
        mid := (right-left)/2+left
        sortMerge(nums, left, mid)
        sortMerge(nums, mid+1, right)
        merge(nums, left, mid, right)
    }

    sortMerge(nums, 0, len(nums)-1)

    return res%1000000007


}