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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型
 */
function InversePairs(nums) {
    // 无序或单调递减的数组才会存在逆序对
    // 无序或单调递减变成单调递增的过程就是把逆序的两个元素交换，消灭掉逆序对
    // 因此只需要在排序过程中将所有交换的次数记录下来即逆序对的总数
    // 归并排序过程中，在右边有序数组元素合并到结果数组时将当前左边数组中未合并的剩余元素个数加起来即逆序对个数
    let count = 0;
    function merge(left, right) {
        const res = [];
        let i = 0;
        let j = 0;
        // 由于左右都是有序的，只需要从头开始对比
        while (i < left.length && j < right.length) {
            if(left[i] <= right[j]){
                res.push(left[i++]);
            }
            else{
                res.push(right[j++]);
                count += left.length - i;
            }
        }
        // 当其中一个数组比较完成后，另一个数组的剩余元素直接加到结果中即可
        return res.concat(left.slice(i)).concat(right.slice(j));
    }
    function mergeSort(arr) {
        if (arr.length < 2) {
            return arr;
        }
        // 递归将数组分成左右两部分并进行合并排序
        let mid = Math.floor(arr.length / 2);
        const left = arr.slice(0, mid);
        const right = arr.slice(mid);
        return merge(mergeSort(left), mergeSort(right));
    }
    mergeSort(nums);
    return count % 1000000007;
}
module.exports = {
    InversePairs: InversePairs,
};