LCR 170. 交易逆序对的总数

分治思想

解题思路

  1. 借助归并排序统计逆序数，而计算逆序数就发生在排序的过程中，利用了「升序排序」以后数组的有序性；

  2. 前面「分」的时候什么都不做，「合」的过程中计算「逆序对」的个数；

  3. 下面看下具体某一次合并的的判断过程：





复杂度

  1. 时间复杂度 O(Nlog⁡N)： 其中 N 为数组长度；归并排序使用 O(Nlog⁡N) 时间；

  2. 空间复杂度 O(N)： 辅助数组 tmp 占用 O(N) 大小的额外空间

代码实现

var reversePairs = function (record) {
    let count = 0;

    const merge = (nums, left, mid, right) => {
        const tmpArr = new Array(right - left + 1);

        let i = left;
        let j = mid + 1;
        let k = 0;

        while (j <= right && i <= mid) {
            if (nums[i] <= nums[j]) {
                tmpArr[k++] = nums[i++];
            } else {
                tmpArr[k++] = nums[j++];
                count += (mid - i + 1);
            }
        }

        while (i <= mid) {
            tmpArr[k++] = nums[i++];
        }
        while (j <= right) {
            tmpArr[k++] = nums[j++];
        }

        for (let i = 0; i < tmpArr.length; i++) {
            nums[i + left] = tmpArr[i];
        }
    };

    const mergeSort = (nums, left, right) => {
        if (left >= right) return;

        let mid = (left + right) >> 1;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        merge(nums, left, mid, right);
    };

    mergeSort(record, 0, record.length - 1);
    return count;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 分治思想
    1. 1.1. 解题思路
    2. 1.2. 复杂度
    3. 1.3. 代码实现