剑指 Offer 51. 数组中的逆序对

题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

1.分治法（归并排序思想）
当left数组的数字比较小时，能确定右边产生多少逆序对

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function (nums) {
    // 分治思想
    // 类似给并排序
    //  a: [5, 7] b: [4, 6] 进行按顺序归并 l, r分别指向a, b 
    //      l         r
    // 1.[4] < [5]，r 右移一位
    // 2.[5] < [6], l 右移一位，发现：b[0:r - 1]的数字都小于 [5]但是在右边，所以产生逆序对
    // 3.[6] < [7], r 右移
    // 4.[7] l 右移, 产生逆序对
    if (nums.length === 0) return 0
    let res = 0
    const merge = (arr, left, right, mid) => {
        const a = arr.slice(left, mid + 1)
        const b = arr.slice(mid + 1, right + 1)
        let l = 0, r = 0, k = left
        while (l < a.length && r < b.length) {
            if (a[l] <= b[r]) {
                arr[k] = a[l]
                k++
                l++
                res += r
            } else {
                arr[k] = b[r]
                k++
                r++
            }
        }
        while (l < a.length) {
            arr[k] = a[l]
            k++
            l++
            res += r
        }
        while (r < b.length) {
            arr[k] = b[r]
            k++
            r++
        }
    }
    const mergeSort = (arr, l, r) => {
        if (l === r) {
            return
        }
        const m = l + ((r - l) >> 1)
        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        merge(arr, l, r, m)
    }
    mergeSort(nums, 0, nums.length - 1)
    return res
};