493. Reverse Pairs

给定一个数组，如果 i < j 且 nums[i] > 2 * nums[j]，将 (i, j) 称作一个逆序对。返回数组中逆序对的数目。

使用归并排序，nums的逆序对数目，等于两个子数组的逆序对数目之和加上左右端点分别位于两个子数组的逆序对数目。在求子数组的逆序对过程中，已将子数组排好序。

为两个数组分别维护指针，对于给定的p指针，不断向右移动，进行判断。

• 时间复杂度O(NlogN)，空间复杂度O(N)
• Runtime: 164 ms, faster than 100.00%
• Memory Usage: 51.6 MB, less than 62.50%

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    if(nums.length === 0) {
        return 0
    }
    return reversePairsRecursive(nums, 0, nums.length - 1)
};

var reversePairsRecursive = function(nums, start, end) {
    if(start === end) {
        return 0
    } else {
        let mid = (start + end) >> 1
        let res = reversePairsRecursive(nums, start, mid) + reversePairsRecursive(nums, mid + 1, end)
        
        let i = start
        let j = mid + 1
        while(i <= mid) {
            while(j <= end && nums[i] > nums[j] * 2) {
                j++
            }
            res += (j - mid - 1)
            i++
        }
        
        const sorted = Array(end - start + 1)
        let p1 = start
        let p2 = mid + 1
        let p = 0
        while(p1 <= mid || p2 <= end) {
            if(p1 > mid) {
                sorted[p++] = nums[p2++]
            } else if(p2 > end) {
                sorted[p++] = nums[p1++]
            } else {
                if(nums[p1] < nums[p2]) {
                    sorted[p++] = nums[p1++]
                } else {
                    sorted[p++] = nums[p2++]
                }
            }
        }
        for(let k = 0; k < sorted.length; k++) {
            nums[start + k] = sorted[k]
        }
        return res
    }
}