老师，我用归并排序思想解逆序对居然超时了，求解。

Question

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

示例 1:

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

限制：

0 <= 数组长度 <= 50000

以下是我的代码

var reversePairs = function(nums) {
    const len = nums.length
    let res = 0

    if (len < 2) return 0

    return getPairs(nums, 0, len - 1)

    function getPairs(arr, left, right) {
        let val = 0

        if (left >= right) {
            return 0
        }

        const mid = Math.floor(left + (right - left)/2)
        val = __getPairs(arr, left, mid, right)
        val += getPairs(arr, left, mid)
        val += getPairs(arr, mid + 1, right)

        return val
    }

    function __getPairs(arr, left, mid, right) {
        let i = left
        let val = 0

        while (i <= mid) {
            for (let j = mid + 1; j <= right; j++) {
                if (arr[i] > arr[j]) {
                    val++
                }
            }
            i++
        }

        return val
    }
};

Answer 1

liuyubobobo 2020-04-25 02:24:32

你的 __getPairs 函数里是一段 O(n^2) 的算法，本质和归并排序中的 merge 不一样。相当于 i 从 left 走到了 mid，对于每一个 i，j 又从 mid + 1 走到了 right。

基于归并排序的思路求逆序对的算法，我写了一个补充的参考代码，可以参考这里（C++）。里面有详细的注释，看是否能看懂？

https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/Optional-04-Inversion-Number/main.cpp

继续加油！：）

• 提问者 qq_朕知道了_1 #1

  非常感谢！

• 提问者 qq_朕知道了_1 #2

  一开始并不理解老师为什么要排序，心想如果排序之后就改变了原有的顺序，求出的逆序对自然也就错了。
  仔细研读之后终于想通了。在归并排序的过程中，当划分的子数组都只有一个元素时，也是对比两个有序数组的逆序对。接着对比有两个元素的子数组，四个元素。。。在不断排序的过程中，把小范围的逆序对累加起来，待排序完成，逆序对也就求解完成。谢谢老师。

• liuyubobobo 回复 提问者 qq_朕知道了_1 #3

  大赞！继续加油！：）