归并排序详解及应用 :: labuladong的算法小抄

[labuladong]

文章链接点这里：归并排序详解及应用

评论礼仪 见这里，违者直接拉黑。

[Days-Go-By]

好难

[zzp-seeker]

493 翻转对题目中
对merge函数的改造代码里：

// 在合并有序数组之前，加点私货

for (int i = lo; i <= mid; i++) {

    // 对于左半边的每个 nums[i]，都去右半边寻找符合条件的元素

    for (int j = mid + 1; j <= hi; k++) {

        // nums 中的元素可能较大，乘 2 可能溢出，所以转化成 long

        if ((long)nums[j] > (long)nums[j] * 2) {

            count++;

        }

    }

}

if ((long)nums[j] > (long)nums[j] * 2) 应改为：if ((long)nums[i] > (long)nums[j] * 2)

[labuladong]

@zzp-seeker 已修正，感谢指出~

[MathsGo]

东哥，文中有个sort, 误打成 srot了

[labuladong]

@MathsGo 感谢指出，已修正~

[yuanzhixiang]

// 进行效率优化，维护左闭右开区间 [mid+1, end) 中的元素乘 2 小于 nums[i]

这里的效率优化同样是双层嵌套，for + while 为什么这样就不超时了？

[Kiiakia]

我原本也没看懂，但是仔细看end是定义在for循环之外的，说明后面的end递增之后，进入下一次循环的过程中，end是不回退的，所以里面的while最多做了hi-mid次，是常数级别的。

[861130245]

人都看傻了

[cheerfulman]

@yuanzhixiang while 里面j不会回退，相当于O(N)复杂度，而for循环j会回退的相当于O(N^2)

[wy-luke]

那么计算区间和 S(i, j) 只需要用 preSum[j] - preSum[i] 就可以计算出来。

感觉这里表述并不是十分严谨

preSum[j] - preSum[i] 对于 nums 数组来说，对应的是 (i, j] 区间的区间和

而题中所给的区间和 S(i, j) 的定义是包含 i 和 j 的

[labuladong]

@wy-luke 你说的有道理，我改下表述

[zhyozhi]

有个地方没想明白，
lower <= preSum[j] - preSum[i] <= upper
这里的 upper > 0 意味着 preSum[j] > preSum[i] ，那 [start, end) 应该也有可能在左侧区间吧？为啥 start 还是从 mid+1 开始的

[Kiiakia]

因为这个是嵌套在merge函数中的，merge本身有了递归，说明左边和右边的已经找好了，就剩下一个在左边，一个在右边的了。

[acse-yw3821]

贴一个cpp版本：315. 计算右侧小于当前元素的个数

class Solution
{
public:
    vector<int> countSmaller(vector<int> &nums)
    {
        int n = nums.size();
        arr.resize(n);
        for (int i = 0; i < n; i++)
            arr[i] = new Pair(nums[i], i);

        // 执行归并排序，本题结果被记录在count中
        count.resize(n, 0);
        tmp.resize(n);
        mergeSort(arr, 0, n - 1);

        return count;
    }

private:
    struct Pair
    {
        int val, id;
        Pair() : val(0), id(0){};
        Pair(int val, int id) : val(val), id(id){};
    };

    vector<Pair *> arr;
    vector<Pair *> tmp; // 归并排序所用的辅助数组
    vector<int> count;  // 记录每个元素后面比自己小的元素个数

    // 归并排序
    void mergeSort(vector<Pair *> &arr, int left, int right)
    {
        if (left >= right)
            return;

        // 归并划分
        int mid = (left + right) / 2;
        // 归并排序左右子数组
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 将两部分有序数组合并为一个有序数组

        for (int k = left; k <= right; k++)
            tmp[k] = arr[k];

        int i = left, j = mid + 1; // 两个指针分别指向左/右子数组的首个元素
        for (int k = left; k <= right; k++)
        {
            if (i == mid + 1)
                arr[k] = tmp[j++];
            else if (j == right + 1 || tmp[i]->val <= tmp[j]->val)
            {
                arr[k] = tmp[i++];
                // 更新count数组
                count[arr[k]->id] += j - mid - 1;
            }
            else
            {
                arr[k] = tmp[j++];
                // 更新count数组
                // count[arr[k]->id] += j - mid - 1;
            }
        }
    }
};

[labuladong]

@zhyozhi 你的理解是对的，但让 start 从 mid + 1 开始不是基于谁大谁小的原因，而是基于归并排序的原理。每次递归处理半个数组，谁都不要多管闲事，否则无法保证不会多算/漏算。

[David-qiuwenhui]

493.翻转对 javascript version

var reversePairs = function(nums) {
    // 用于辅助合并有序数组
    let temp = new Array(nums.length);
    let count = 0;

    // 定义 将子数组nums[left...right]进行排序
    function sortNums(nums, left, right) {
        // base case
        if (left >= right) {
            return;
        }

        // 防止溢出
        let mid = Math.floor(left + (right - left) / 2);
        // 先对左半部分数组nums[left...mid]排序
        sortNums(nums, left, mid);
        // 再对右半部分数组nums[mid+1...right]排序
        sortNums(nums, mid + 1, right);

        // 将两部分有序数组合并成一个有序数组
        merge(nums, left, mid, right);
    }

    // 定义 将nums[left...mid]和nums[mid+1...right]这两个有序数组合并成一个有序数组
    function merge(nums, left, mid, right) {
        // 先把nums[left...right]复制到辅助数组中
        // 以便合并后的结果能够直接存入nums
        for (let n = left; n <= right; n++) {
            temp[n] = nums[n];
        }

        // 在合并有序数组之前，加点私货
        let m = left, n = mid + 1;
        while (m <= mid ) {
            // 对左半边的nums[m] 寻找符合条件的最大n值
            while (n <= right && nums[m] > 2 * nums[n]) {
                n++;
            }
            // 符合条件的元素个数等于n到mid-1之间的距离
            count += n - mid -1;
            m++;
        };

        // 数组双指针技巧 合并两个有序数组
        let i = left, j = mid + 1;
        for (let p = left; p <= right; p++) {
            if (i == mid + 1){
                // 左半边数组已全部被合并
                nums[p] = temp[j++];
            } else if (j == right + 1) {
                // 右半边数组已全部被合并
                nums[p] = temp[i++];
            } else if (temp[i] < temp[j]) {
                nums[p] = temp[i++];
            } else if (temp[i] >= temp[j]) {
                nums[p] = temp[j++];
            }
        }
    }

    // 排序整个数组（原地修改）
    sortNums(nums, 0, nums.length - 1);
    return count;
};

[Matilda-Yxx]

315有些不明白，如果用Pair记录元素位置，那么题目如果给出了有重的test case数组，要怎么处理呢？

[xiewenya]

由于用Pair替代了原有的int元素，那么即使数组中有重复的val，但因为他们的idx不同，所有Pair不同。
换句话说，即使在原数组中有重复的val，但是生成Pair之后，他们就是不同的Object了，所以Pair[]数组中不存在重复元素。

[zhaoedf]

翻转对的一个等价写法，感觉容易理解一点。

        p1 = low
        p2 = mid+1
        j = low
        # print(nums)
        while p1 <= mid:
            # print(low, high, i, nums[i])
            if nums[p1][1] > 2*nums[p2][1]:
                self.count += (mid+1-p1)
                p2 += 1
                if p2 == high+1:
                    break       
            else:
                p1 += 1     

[BailingZhann]

一刷打卡，属实有点难哇。希望二刷能更理解，但真的学到很多。谢东哥！！

[GoingMyWay]

327题有一点想不通的是为什么start和end要定义为以下的初始值？

int start = mid + 1, end = mid + 1;

[weixueman]

315题，归并时要注意当前比较的两个数相等的情况

[bruceeewong]

20230118 打卡

[xiewenya]

315我理解本质是求排序后，原有的元素向右移动了多少位。
因此每次在merge的时候是需要计算merge后享有移动了多少位。贴一下我的版本；
另外我理解这道题也可以用快排解决？

class Solution {
    private static class Pair{
        int val;
        int idx;

        public Pair(int val, int idx){
            this.val = val;
            this.idx = idx;
        }
    }

    private Pair[] helper;
    private int[] count;
    private Pair[] pairs;

    public List<Integer> countSmaller(int[] nums) {
        helper = new Pair[nums.length];
        count = new int[nums.length];
        pairs = new Pair[nums.length];

        for (int i = 0; i < nums.length; i++){
            pairs[i] = new Pair(nums[i], i);
        }

        mergeSort(pairs, 0, nums.length - 1);
        List<Integer> res = new LinkedList<>();
        for (int i = 0; i < nums.length; i++){
            res.add(count[i]);
        }

        return res;
    }

    private void mergeSort(Pair[] pairs, int left, int right){
        if (left >= right){
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(pairs, left, mid);
        mergeSort(pairs, mid + 1, right);
        merge(pairs, left, mid, right);
    }

    private void merge(Pair[] pairs, int left, int mid, int right){
        int start1 = left;
        int start2 = mid + 1;
        int idx = left;

        while(start1 <= mid && start2 <= right){
            if (pairs[start1].val <= pairs[start2].val){
                // 元素向左移动，说明左边有比它大的元素；向右移动，说明右边有比它小的元素。
                // 因此我们只需要计算向右移动的步数；
                count[pairs[start1].idx] += idx > start1 ? idx - start1 : 0;
                helper[idx++] = pairs[start1++];
            } else {
                count[pairs[start2].idx] += idx > start2 ? idx - start2 : 0;
                helper[idx++] = pairs[start2++];
            }
        }
        while (start1 <= mid){
            count[pairs[start1].idx] += idx > start1 ? idx - start1 : 0;
            helper[idx++] = pairs[start1++];
        }
        while (start2 <= right){
            count[pairs[start2].idx] += idx > start2 ? idx - start2 : 0;
            helper[idx++] = pairs[start2++];
        }

        for (int i = left; i <= right; i++){
            pairs[i] = helper[i];
        }
    }
}

[daiyanze]

题目912，通用 merge 函数 双指针合并有序数组 那部分。

在合并两个有序数组的时候，感觉有行代码块用不上 arr[p] = temp[j++];。 我把这部分注释之后提交了一下，发现可以正常AC通过。Debug的时候发现 p == j。有点神奇。。。
想知道有没有人可以解释一下

if (i == mid + 1) {
  arr[p] = temp[j++];
} else if (j == hi + 1) {

[daiqian0930]

temp数组本身就是arr数组copy过去的（arr数组的后半部分的默认值就是temp数组），当i==mid+1,说明左侧的数组归并完毕，只需要将右侧数组剩下待归并的部分（索引是j-hi）copy到arr。后半部分默认值就是temp数组，所以也就不用再拷贝了。

[Jack-cin]

c++版（chatgpt不太行）

class Solution {
private:
    vector<long> temp;
    //将 问题对象 转化为 前缀和
    vector<long> preSum;//-2^31<=nums[i]<=2^31-1
    int lower, upper;
    int count = 0;

public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        //变成全局变量
        this->lower = lower;
        this->upper = upper;
        //计算前缀和
        preSum.resize(nums.size()+1);
        for (int i = 1; i <=nums.size(); i++) {
            preSum[i] = nums[i-1] + preSum[i-1];
        }
        //归并排序
        temp.resize(nums.size()+1);
        sort(preSum, 0, preSum.size()- 1);
        return count;
    }

    void sort(vector<long>& nums, int lo, int hi) {
        if (lo == hi)return;

        int mid = lo + (hi - lo) / 2;
        sort(nums, lo, mid);
        sort(nums, mid + 1, hi);
        merge(nums, lo, mid, hi);
    }

    void merge(vector<long>& nums, int lo, int mid, int hi) {
        for (int i = lo; i <= hi; i++) temp[i] = nums[i];

        //核心代码： 
        //获得j数组的左闭右开区间[start, end)，使得差(即区间和)在[lower, upper]中
        int start = mid + 1, end = mid + 1;
        for (int i = lo; i <= mid; i++) {
            while (start <= hi && nums[start] - nums[i] < lower) {
                start++;
            }//直到start满足nums[start]-nums[i] >= lower
            while (end <= hi && nums[end] - nums[i] <= upper) {
                end++;
            }//直到end不满足nums[end]-nums[i]<=upper
            count += end - start;
        }

        int i = lo, j = mid + 1;
        for (int p = lo; p <= hi; p++) {
            if (i == mid + 1) {
                nums[p] = temp[j++];
            } else if (j == hi + 1) {
                nums[p] = temp[i++];
            } else if (temp[i] > temp[j]) {
                nums[p] = temp[j++];
            } else {
                nums[p] = temp[i++];
            }
        }
    }
};

[Bymanman]

new long[nums.length + 1];里面多出来的perSum[0]=0对后面排序的个数为什么没有影响吗？

[chengrongkai]

mark一下，后续再来深度学习下

[xiehuacheng]

327 区间和个数
C++题解中多了一行sort(preSum.begin(), preSum.end());
这应该是gpt生成错了

[Chris-zhang1]

东哥为啥第一题在leetcode正常写归并python会超时啊

[miiiiiko]

是说315题吗，我也一样，不知道为啥超时

[miiiiiko]

感觉翻转对有点没解释清楚，最终解法时间复杂度低的原因是end不会回退，所以虽然表面上看是for嵌套while, 但是实际上这一步是每层o(n)的复杂度，下面merge也是每层o(n)的复杂度，一共logn层，所以复杂度是o(nlogn)

[lithiumhydride2]

327 c++解法

//leetcode submit region begin(Prohibit modification and deletion)
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

template<class T>
class Merge {
protected:
    // 静态成员变量需要在 类外声明
    vector<T> temp;
private:
    // 归并函数
    virtual void merge(vector<T>& nums,int low,int mid,int high) {
        // 将 nums[low,high]复制到 temp 中
        for (int l = low; l <= high ; ++l) {
            temp[l] = nums[l];
        }
        // 双指针 ， 合并两个有序数组
        int i = low ,j = mid + 1;
        for (int k = low; k <= high; ++k) {
            if( i == mid + 1){
                // 左半边已经合并
                nums[k] = temp[j++];
            } else if (j == high + 1){
                // 右边已经合并
                nums[k] = temp[i++];
            } else if (temp[i] > temp[j]){
                // 排序的大小在此处产生
                nums[k] = temp[j++];
            } else {
                nums[k] = temp[i++];
            }
        }
    }
public:

    void sort(vector<T>& nums){
        // 占用内存
        temp.resize(nums.size());
        // 对整个数组原地排序
        sort(nums,0,nums.size()-1);
    }

    // 将子数组 nums[low, high]进行排序
    // 静态成员函数 只能调用 静态成员变量与函数
    void sort(vector<T>& nums,int low ,int high){
        if(low == high) return;
        // 归并排序
        int mid = low + (high - low) / 2;
        sort(nums,low,mid);
        sort(nums,mid+1,high);
        // 归并子问题
        merge(nums,low,mid,high);
    }
};

class Solution:Merge<long> {
private:
    vector<long> pre_sum;
    vector<long> temp;
    int count = 0;
    int _lower,_upper;
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        // 构建前缀和数组
        _lower = lower;
        _upper = upper;
        pre_sum.resize(nums.size() + 1);
        pre_sum[0] = 0;
        for (int i = 1; i <= nums.size() ; ++i)
            pre_sum[i] = pre_sum[i - 1] + nums[i-1];
        // pre_sum[j + 1 ] - pre_sum[i] =  nums[i] + ... + nums[j]
        temp.resize(nums.size() + 1);
        Merge::sort(pre_sum,0,pre_sum.size()-1);
        return count;
    }
    // 覆写基类
    void merge(vector<long>& nums,int low,int mid,int high) override{
        //
        int start = mid + 1 , end = mid + 1;
        for (int i = low; i <= mid; ++i) {
            // 不满足条件 start 变大 ， 停止时满足 >= lower
            while (start <= high && nums[start] - nums[i] < _lower)
                start++;
            // end 停止时 不满足条件了
            while (end <= high && nums[end] - nums[i] <= _upper)
                end ++;
            count += end - start;
        }

         // 将 nums[low,high]复制到 temp 中
        for (int l = low; l <= high ; ++l) {
            temp[l] = nums[l];
        }
        // 双指针 ， 合并两个有序数组
        int i = low ,j = mid + 1;
        for (int k = low; k <= high; ++k) {
            if( i == mid + 1){
                // 左半边已经合并
                nums[k] = temp[j++];
            } else if (j == high + 1){
                // 右边已经合并
                nums[k] = temp[i++];
            } else if (temp[i] > temp[j]){
                // 排序的大小在此处产生
                nums[k] = temp[j++];
            } else {
                nums[k] = temp[i++];
            }
        }

    }
};

[GuochenLiao]

问题：在count of range题目中，prefix array在被sort后还有相同的意义吗？感觉这里让我有点晕乎