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

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

示例 1:

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

限制：

0 <= 数组长度 <= 50000

解法：归并排序

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    if(nums.length == 0) return 0;
    let resArr = new Array(nums.length).fill(0);
    const res = mergeSortCount(nums,0,nums.length-1,resArr);
    return res;
};

var mergeSortCount = function(nums,left,right,resArr){
    if(left == right) return 0;
    let mid = Math.floor((left + right) / 2);
    const leftCount = mergeSortCount(nums,left,mid,resArr);
    const rightCount = mergeSortCount(nums,mid+1,right,resArr);
    const allCount = mergeCount(nums,left,right,resArr);
    return leftCount + rightCount + allCount;
}

var mergeCount = function(nums,left,right,resArr){
    let count = 0;
    let end1 = parseInt((left + right)/2);
    let start2 = end1+1;
    let idx1 = left;
    let idx2 = start2;
    while(idx1<=end1&&idx2<=right){
        if(nums[idx1]<=nums[idx2]){
            resArr[idx1+idx2-start2] = nums[idx1++];
        }else{
            count += end1 - idx1 + 1;
            resArr[idx1+idx2-start2] = nums[idx2++];
        }
    }

    while(idx1<=end1){
        resArr[idx1+idx2-start2] = nums[idx1++];
    }

    while(idx2<=right){
        resArr[idx1+idx2-start2] = nums[idx2++];
    }

    while(left<=right){
        nums[left] = resArr[left++];
    }

    return count;
}