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

package main

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

func InversePairs( nums []int ) int {
    // write code here
    ans := 0
    mergeSort(nums, 0, len(nums)-1, &ans)
    return ans
}

func mergeSort(nums []int, left, right int, ans *int) {
    if left < right {
        mid := (right-left)/2 + left
        mergeSort(nums, left, mid, ans)
        mergeSort(nums, mid+1, right, ans)
        merge(nums, left, mid, right, ans)
    }
}

func merge(nums []int, left, mid, right int, ans *int) {
    temp := make([]int, right-left+1)
    i, j, idx := mid, right, len(temp)-1
    for i >= left && j >= mid+1 {
        if nums[i] > nums[j] { // 比 j 之前所有元素都大（j 是 mid+1->j 最大的））
            *ans += j-mid
            *ans %= Mod
            temp[idx] = nums[i]
            idx--
            i--
        } else {
            temp[idx] = nums[j]
            idx--
            j--
        }
    }
    for i >= left {
        temp[idx] = nums[i]
        idx--
        i--
    }
    for j >= mid+1 {
        temp[idx] = nums[j]
        idx--
        j--
    }
    copy(nums[left:right+1], temp)
}