题解 | 数组中的逆序对

package main

func InversePairs(nums []int) int {
    tmp := make([]int, len(nums))
    var left, right int
    right = len(nums) - 1

    res := mergeSort(nums, tmp, left, right)

    return res % 1000000007
}

func mergeSort(nums, tmp []int, left, right int) int{
    count := 0
    if left >= right{
        return count
    }

    mid := (left+right) / 2

    // 递归调用 分
    count_left := mergeSort(nums, tmp ,left, mid)
    count_right := mergeSort(nums, tmp , mid+1, right)
    // 合并递归 治
    count_now := merge(nums, tmp ,left, mid, right) 

    return (count_left + count_right + count_now)
}

func merge(nums, tmp []int, left, mid, right int) int{
    count := 0
    var i, j, t int
    t = left
    i = left
    j = mid + 1

    for i <= mid && j <= right{
        if nums[i] > nums[j]{
            tmp[t] = nums[j]
            j++
            count += mid - i + 1
        } else{
            tmp[t] = nums[i]
            i++
        }
        t++
    }

    for i <= mid{
        tmp[t] = nums[i]
        i++
        t++
    }

    for j <= right{
        tmp[t] = nums[j]
        j++
        t++
    }

    for p:=left; p<=right; p++{
        nums[p] = tmp[p]
    }

    return count
}

tmp 负责收集 下标 left 到 right 的原始

注意 i j t 的初始值

return res % 1000000007