【专题八】分治——归并排序

📝前言说明：

• 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

什么是归并排序

可以先看看这篇文章： 排序——归并排序

这里我自己做一下总结：

• 归并排序：递归
• 选一个mid，对左边区域进行排序
• 左边区域排序也是：先选一个mid，然后对左边进行排序
• 直到左边区间只有一个元素的时候，返回
• 然后对右边区域进行排序
• 当两个区域都向上返回以后，需要合并有序数组
• 一直层层往上返回到整个数组

最关键的两步：

• 分左右区间
• 两个区域都返回时，合并两个有序数组

归并和快排对比

• 归并和快排都是把数组分块，只是两个算法对数据的处理时机不同
• 归并：本层的操作是：先搞孩子，在左右都返回以后，进行合并数组（像：后序遍历）
• 快排：本层的操作：得到一层，就直接在本层就把数组分两块了。（像：前序遍历）

912. 排序数组

题目链接：https://leetcode.cn/problems/sort-an-array/description/

优质解

思路：

• 题目没什么好说的，用于练习归并排序写法

代码：

class Solution {
public:
    vector<int> tmp;
    vector<int> sortArray(vector<int>& nums) 
    {
        tmp.resize(nums.size()); // 提前开空间
        mergesort(nums, 0, nums.size() - 1);
        return nums;
    }

    void mergesort(vector<int>& nums, int left, int right)
    {
        if(left >= right) return;
        int mid = (left + right) >> 1;
        mergesort(nums, left, mid);
        mergesort(nums, mid + 1, right);
        int i = 0, l = left, r = mid + 1;
        while(l <= mid && r <= right)
            tmp[i++] = nums[l] <= nums[r] ? nums[l++] : nums[r++];
        while(l <= mid) tmp[i++] = nums[l++];
        while(r <= right) tmp[i++] = nums[r++];
        for(int i = 0; i < right - left + 1; i++)
            nums[i + left] = tmp[i];
    }
};

时间复杂度：O(nlogn)
空间复杂度：O(n)

LCR 170. 交易逆序对的总数

题目链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

优质解

思路：

• 题意：找出所有 record[i] > record[j] 且 i < j 的元素对
• 暴力解法：枚举所有元素对→时间复杂度O($n^2$)
• 把数组划分成两部分，左半部分和右半部分：
  • 假设左半部分逆序对为 a 个，右边为 b个，然后再一左一右拿一个元素组成的逆序对共有c个，则整个数组的逆序对共：a + b + c个
  • 优化的点在哪？在一左一右拿元素的地方，因为左半部分的下标 < 右半部分的下标，所以此时拿元素只需要满足：左半部分拿的元素比右半部分拿的元素大就可以了。（就可以引出下面的方法）
    • 左半部分得到a → 左排序 → 再右半部分得到b → 右排序 → 再一左一右挑【这时候，我们就可以利用排序的有序性】
    • 在一左一右挑的时候，左边挑完一个数nums[left]，在右边找到刚好小于nums[left]的nums[right]，又因为数组有序，就可以快速得到nums[left]对应的逆序对的数目
• 归并排序解决
  • 一个数组的有序对个数 = 左 + 右 + 基于左右的选择（这像不像归并排序的左有序 + 右有序 + 合并左右数组）
  • 左半部分的个数以及右半部分的个数的求法又用同样的 方法分割成a + b + c，于是左半部分和右半部分的结果已经在递归返回时得到了。
  • 核心就变成了求对有序的左边和有序的右边，一左一右取，求c：
    • nums[left] <= nums[right]：left++（因为有序，会让nums[left]变大）
    • nums[left] > nums[right]：因为有序，则 left右边的所有元素都比nums[right]大。一次得到多个逆序对。然后right++看后一个数。

如果是降序呢？
降序的话，就需要分清楚 “得到更多信息” 的是那一边，这时候是，如果满足要求，则 right左边的元素一定都比nums[left]小

代码：

class Solution {
public:
    vector<int> tmp;
    int ans = 0;
    int mergesort(vector<int>& record, int l, int r)
    {
        int c = 0;
        if(l >= r) return 0;
        int mid = (l + r) >> 1;
        int left_ans = mergesort(record, l, mid);
        int right_ans = mergesort(record, mid + 1, r);
        int left = l, right = mid + 1, i = 0;
        while(left <= mid && right <= r) 
        {
            // 在这里已经是 [l, mid] 和 [mid + 1, r] 已经分别排序好了
            // 在合并的时候得到，进行判断并计算 c
            if(record[left] <= record[right])
                tmp[i++] = record[left++];
            else
            {
                c += (mid - left + 1);
                tmp[i++] = record[right++];
            }
        }
        while(left <= mid)
            tmp[i++] = record[left++];
        while(right <= r)
            tmp[i++] = record[right++];
        for(int i = 0; i < r - l + 1; i++)
            record[i + l] = tmp[i];
        return c + left_ans + right_ans;
    }
    int reversePairs(vector<int>& record) 
    {
        tmp.resize(record.size());
        ans = mergesort(record, 0, record.size() - 1);
        return ans;
    }
};

时间复杂度：O(nlogn) 同归并排序
空间复杂度：O(n)

315. 计算右侧小于当前元素的个数

题目链接：https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/

个人解

没搞出来，有部分思路：

    // ans[i] 始终代表该元素在目前所在的数组已经统计好的数据
    // 分成左区域和右区域有序
    // 一个数 x 如果在左区域（如果刚好对应数组的下标是 i ）：ans[i] == ans[i]（因为左区域已经统计过） + 右区域比 x 小的（因为右区域的元素下标一定大于左区域的元素）
    // 一个数如果在右区域：nums[i] 就不用变化
    // 关键在于处理合并的时候：要统计（更新）右边比它小的个数 c ，然后更新 nums[i]
    // 但是随着排序，x 会移动，我们可以用哈希表记录 x 对应的下标，但是出现重复元素呢？【卡在这里】

优质解

思路：

关键：有重复元素，哈希表无法映射对应的下标怎么办？

• 自己创建一个相同的数组index，记录对应位置的下标，然后绑定移动
• 如，5的原始下标为1，然后被移动到了下标3，此时index里5的原始下标也被移动到了下标3，也就是index[5的下标] == 5的原始下标

代码：

class Solution {
public:
    vector<int> tmp;
    vector<int> ans;
    vector<int> index; // 这个还不能写成 vector<int> index(5001)
    vector<int> tmp_index;

    void mergesort(vector<int>& nums, int l, int r)
    {
        if(l >= r) return;
        int mid = (l + r) >> 1;
        mergesort(nums, l, mid);
        mergesort(nums, mid + 1, r);
        int left = l, right = mid + 1, i = 0;
        while(left <= mid && right <= r)
        {
            if(nums[left] > nums[right])
            {
                ans[index[left]] += r - right + 1; // 更新答案
                tmp[i] = nums[left]; // 注意这里不要 ++
                tmp_index[i++] = index[left++]; // 绑定的数组跟着动 
            }
            else
            {
                tmp[i] = nums[right];
                tmp_index[i++] = index[right++];
            }
        }
        while(left <= mid)
        {
            tmp[i] = nums[left];
            tmp_index[i++] = index[left++];
        }
        while(right <= r)
        {
            tmp[i] = nums[right];
            tmp_index[i++] = index[right++];
        }
        for(int i = 0; i < r - l + 1; i++)
        {
            nums[i + l] = tmp[i];
            index[i + l] = tmp_index[i];
        }
    }

    vector<int> countSmaller(vector<int>& nums) 
    {
        int n = nums.size();
        ans.assign(n, 0);
        tmp.resize(n);
        index.resize(n);
        tmp_index.resize(n);

        for (int i = 0; i < n; i++) {
            index[i] = i;
        }

        mergesort(nums, 0, n - 1);
        return ans;
    }
};

时间复杂度：O(nlogn)
空间复杂度：O(n)

493. 翻转对

题目链接：https://leetcode.cn/problems/reverse-pairs/description/

个人解

思路：

• 归并排序，类似第 170 题
• 但是，这里不能将合并操作和统计操作合在一起
• 我们需要在合并数组之前完成翻转对的统计

用时：
屎山代码：

class Solution {
public:
    vector<int> tmp;

    int mergesort(vector<int>& nums, int l, int r)
    {
        int ans = 0;
        if(l >= r) return 0;
        int mid = (l + r) >> 1;
        ans += mergesort(nums, l, mid);
        ans += mergesort(nums, mid + 1, r);
        int left = l, right = mid + 1, i = 0;

        // 先统计翻转对
        while(right <= r) // 如果右侧完全没元素了，则不可能再有翻转对
        {
            while(left <= mid && (nums[left] / 2.0 <= nums[right])) // 换成除防溢出
                left++; // 不满足要求时，left++ 找满足要求的
            if(left > mid)
                break; // 左侧没元素了，也不可能再有翻转对
            ans += (mid - left + 1) ; // left及left右侧的元素都可以和 nums[right]组成翻转对
            right++; // 找下一个
        }
        // 合并数组
        left = l, right = mid + 1, i = 0;
        while(left <= mid && right <= r)
            tmp[i++] = nums[left] < nums[right] ? nums[left++] : nums[right++];
        while(left <= mid) tmp[i++] = nums[left++];
        while(right <= r) tmp[i++] = nums[right++];
        for(int i = 0; i < r - l + 1; i++)
            nums[i + l] = tmp[i];
        return ans;
    }
    int reversePairs(vector<int>& nums) 
    {
        tmp.resize(nums.size());
        return mergesort(nums, 0, nums.size() - 1);
    }
};

时间复杂度：O(nlogn)，每层 n 次遍历，递归 logn 层
空间复杂度：O(n)

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！