描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对 1000000007 取模的结果输出。 即输出P mod 1000000007

数据范围： 对于 50% 的数据, size≤104
对于 100% 的数据, size≤105

数组中所有数字的值满足 0 ≤val≤1000000

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

输入描述：题目保证输入的数组中没有的相同的数字

示例

// 输入：
[1,2,3,4,5,6,7,0]
// 返回值：
7

// 输入：
[1,2,3]
// 返回值：
0

解题思路

归并排序

代码实现

var count int = 0

/**
 * 归并排序法
 *
 * @param data int 整型一维数组
 * @return int 整型
 */
func inversePairs(data []int) int {
    n := len(data)
    if n < 2 {
        return 0
    }

    mergeSort(data, 0, len(data)-1)

    return count
}

func mergeSort(arr []int, left int, right int) {
    if left >= right {
        return
    }

    mid := left + (right-left)/2

    mergeSort(arr, left, mid)
    mergeSort(arr, mid+1, right)

    merge(arr, left, mid, right)
}

func merge(arr []int, left int, mid int, right int) {
    result := make([]int, right-left+1)
    c, s, l, r := 0, left, left, mid+1

    for l <= mid && r <= right {
        if arr[l] <= arr[r] {
            result[c] = arr[l]
            l++
        } else {
            count += mid + 1 - l
            count %= 1000000007

            result[c] = arr[r]
            r++
        }
        c++
    }

    for l <= mid {
        result[c] = arr[l]
        c++
        l++
    }

    for r <= right {
        result[c] = arr[r]
        c++
        r++
    }

    for i := 0; i < len(result); i++ {
        arr[s] = result[i]
        s++
    }
}