题解 | BM20 数组中的逆序对

function InversePairs(data) {
    // write code here
    let mod = 1000000007;
    let temp = [];
    function mergeNode(l, r) {
        // 停止划分
        if (l >= r) return 0;
        // 取中位数下标
        let mid = parseInt((l + r) / 2);
        let ans = mergeNode(l, mid) + mergeNode(mid + 1, r);
        ans %= mod;
        // 保存原数组数据
        for (let i = l; i <= r; ++i) {
            temp[i] = data[i];
        }
        let left = l,
            right = mid + 1;
        for (let i = l; i <= r; ++i) {
            if (left == mid + 1) {
                // 左指针到头，则赋值右边
                data[i] = temp[right++];
            } else if (right == r + 1 || temp[left] <= temp[right]) {
                // 右指针到头或左小于等于右，则赋值左边
                data[i] = temp[left++];
            } else {
                // 右边大于左边，则赋值右边并统计逆序对
                data[i] = temp[right++];
                ans = ans + mid - left + 1;
            }
        }
        // 答案取模
        return ans % mod;
    }

    let len = data.length;
    let ans = mergeNode(0, len - 1);
    // console.log("index:", index);
    return ans;
}
module.exports = {
    InversePairs: InversePairs,
};