自学内容网 自学内容网
自学内容网 > 正文

归并排序思想以及做题技巧总结

🕗 发布于 2024-12-01 06:39 排序算法  算法  数据结构  归并排序  

目录

手撕归并排序

题目一：逆序对总数

题目二：计算右侧小于当前元素个数

题目三：翻转对

博主主页：东洛的克莱斯韦克-CSDN博客

手撕归并排序

        912. 排序数组 - 力扣（LeetCode）

        归并排序相当于二叉树的后续遍历，在向上递归的过程中，把左右两个区间的有序数组合并。

        给定一个数组，先递归到数组的最低端

        然后向上归并，归并过程相当于合并两个有序数组，每一层需要O(N)时间复杂度把数组合并成有序，一共有logN层，所以归并排序的时间复杂度为O(NlogN)

class Solution {
    vector<int> _tmp;
public:
    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 - left) / 2;

        //递归
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        //合并有序数组
        int cur1 = left, cur2 = mid + 1, i = left;
        while(cur1 <= mid && cur2 <= right)
            nums[cur1] <= nums[cur2] ? _tmp[i++] = nums[cur1++] : _tmp[i++] = nums[cur2++];
        
        //左区间 或 右区间 可能有数据没处理
        while(cur1 <= mid)
            _tmp[i++] = nums[cur1++];

        while(cur2 <= right)
            _tmp[i++] = nums[cur2++];

        //把排好序的数组拷贝到 nums 中
        for(int i = left; i <= right; i++)
            nums[i] = _tmp[i];
    }
};

        左右区间单调性分析

        归并排序的时间复杂度和快排一样，但合并两个有序数组时需要额外的空间，如果单纯排序的话推荐使用快排。

        而归并排序时，左右区间都有单调性并且有序，我们可以利用这样的过程解决一些问题。

题目一：逆序对总数

LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

        题目要求我们找逆序对总数，逆序对满足一下条件：

        i < j   &&   nums[i] > nums[j]

        暴力解法如下：

        首先用一个变量保存逆序对数量 int ret = 0;

        第一层 for 循环固定一个数 nums[i] ， 第二层 for 循环遍历该数之后的所有数 nums[j]

                如果nums[i] > nums[j] 为真， ret++;

        暴力解法相当于枚举了所有组合，时间复杂度为O(N^2), 空间复杂度为O(1)。

        这里我们思考一下，我们之所以要枚举所有组合，是因为数组是无序的。那如果数组是有序的话是不是不必枚举所有组合从而优化时间复杂度。

        如果我们先给数组排序，我们就不知道数组的原始下标，因为逆序对需要满足 i < j 这一条件，我们这里的策略可以是一边排序一边找逆序对的数量。

        这里归并排序的过程和查找逆序对的过程可以完美契合：

                1.归并排序中每一层的左右区间都是有序的

                2.归并排序在合并两个有序数组时要遍历一遍左右区间

        这里我们应该思考归并排序能否帮我们枚举到所有正确结果：

                对于一个数组而言，我们遍历一边就可以枚举出所有数据。我们把数组分成左右两个区间，先去左区间找出所有逆序对，再去右区间找出所有逆序对，再一左一右区间找剩余的逆序对。

        对于归并排序而言，我们只需探讨一左一右区间即可，因为下一层的一左一右区间是上一层的左区间或右区间。

        前文已经分析过左右区间的单调性了，这里我们讨论一下“左右区间用升序还是降序”

这里总结一下：

        策略一，左区间有多少个数比右区间的某个数大：归并排序用升序

        策略二，右区间有多少个数比左区间的某个数小：归并排序用降序

        策略三，左区间有多少个数比右区间的某个数小：归并排序用降序

        策略四，右区间有多少个数比左区间的某个数大：归并排序用升序

代码示例：

class Solution {
    vector<int> _tmp;
public:
    int reversePairs(vector<int>& record) {
        _tmp.resize(record.size());
        return mergeSort(record, 0, record.size() - 1);
    }

    int mergeSort(vector<int>& nums, int left, int right) {

        if(left >= right) return 0;

        int mid = left + (right - left) / 2;

        //去左区间 和 右区间里寻找
        int ret = 0;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);

        //一左一右区间寻找
        int cur1 = left, cur2 = mid + 1, i = left;
        while(cur1 <= mid && cur2 <= right) {
            if(nums[cur1] > nums[cur2]) {
                ret += mid - cur1 + 1;
                _tmp[i++] = nums[cur2++];
            }
            else {
                _tmp[i++] = nums[cur1++];
            }
        }

        //添加左区间或右区间没有处理完的数据
        while(cur1 <= mid) _tmp[i++] = nums[cur1++];
        while(cur2 <= right) _tmp[i++] = nums[cur2++];

        //把排好序的数组cp到原数组中
        for(int j = left; j <= right; j++) 
            nums[j] = _tmp[j];
        
        //返回结果
        return ret;
    }
};

题目二：计算右侧小于当前元素个数

        这题很明显是 右区间有多少个数比左区间的某个数小 这一条件，可以用归并排序的过程来求解，但我们还要知道某个数的原始下标才可以，我们可以用一个index数组（数组初始化为 0， 1， 2， 3 ......）和nums数组绑定——nums数组中的数据怎么挪动，index数组中的数据就怎么挪动，这样我们可以通过index数组找到某个数的原始下标

class Solution {
    vector<int> _ret;      //存储最终结果
    vector<int> _tmp;     //归并排序用到的临时变量
    vector<int> _index;  //原始下标
    vector<int> _tmp_index; 
public:
    vector<int> countSmaller(vector<int>& nums) {

        int n = nums.size();
        _ret.resize(n);
        _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 _ret;
    }

    void mergeSort(vector<int>& nums, int left, int right) {

        if(left >= right) return;
        
        //分别去左边寻找 和 右边寻找
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        //归并
        int cur1 = left, cur2 = mid + 1, i = left;
        while (cur1 <= mid && cur2 <= right) {
            if(nums[cur1] > nums[cur2]) {
                _ret[_index[cur1]] += right - cur2 + 1;
                _tmp[i] = nums[cur1];
                _tmp_index[i] = _index[cur1];
                ++i; ++cur1;
            }
            else{
                _tmp[i] = nums[cur2];
                _tmp_index[i] = _index[cur2];
                ++i; ++cur2;
            }
        }
        
        //处理左区间或有区间剩余数据
        while(cur1 <= mid) {
            _tmp[i] = nums[cur1];
            _tmp_index[i] = _index[cur1];
            ++i; ++cur1; 
        }
        while(cur2 <= right) {
            _tmp[i] = nums[cur2];
            _tmp_index[i] = _index[cur2];
            ++i; ++cur2;
        }

        //把临时空间上排好序的数据拷贝到临时空间
        for(int i = left; i <= right; i++) {
            nums[i] = _tmp[i];
            _index[i] = _tmp_index[i];
        }
    }
};

题目三：翻转对

493. 翻转对 - 力扣（LeetCode）


原文地址：https://blog.csdn.net/2301_79796701/article/details/144060287

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024