题解 | #数组中的逆序对#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型
 */

function Inverse(nums, left, right) {
    if (left >= right-1) {
        return [0, nums];
    }
    let mid = Math.floor((left + right) / 2);
    let [leftCount, leftList] = Inverse(nums.slice(0, mid),0,mid);
    let [rightCount, rightList] = Inverse(nums.slice(mid),0,nums.length-mid);
    let returnList = [];
    let thisCount = leftCount+rightCount;
    // console.log(thisCount)

    p1 = 0;
    p2 = 0;
    while (p1 < leftList.length || p2 < rightList.length) {
        if (p1 >= leftList.length) {
            returnList.push(...rightList.slice(p2));
            break
        }
        if (p2 >= rightList.length) {
            returnList.push(...leftList.slice(p1));
            break
        }

        if (leftList[p1] > rightList[p2]) {

            thisCount += rightList.length - p2;
            returnList.push(leftList[p1]);
            p1++;
        } else {
            // thisCount += leftList.length - p1;
            returnList.push(rightList[p2]);
            p2++;
        }
    }
    // console.log(returnList)
    return [thisCount,returnList]
}

function InversePairs(nums) {
    // write code here
    const modN = 1000000007;
    let left = 0;
    let right = nums.length;
    let [thisCount,returnList]=Inverse(nums, left, right)
    return thisCount % modN
}
module.exports = {
    InversePairs: InversePairs,
};