Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >归并排序应用——剑指 Offer 51. 数组中的逆序对

归并排序应用——剑指 Offer 51. 数组中的逆序对

作者头像
lovevivi
发布于 2022-12-10 06:36:55
发布于 2022-12-10 06:36:55
50700
代码可运行
举报
文章被收录于专栏:萌新的日常萌新的日常
运行总次数:0
代码可运行

开启掘金成长之旅!这是我参与「掘金日新计划 · 12 月更文挑战」的第10天,点击查看活动详情 @TOC

题目

1.在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

示例 1: 输入: [7,5,6,4] 输出: 5

1.错误示范

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
int reversePairs(int* nums, int numsSize) {
    int i = 0;
    int j = 0;
    int sum = 0;
    for (i = 0; i < numsSize; i++)
    {
        for (j = i + 1; j < numsSize; j++)
        {
            if (nums[i] > nums[j])
            {
                sum++;
            }
        }
    }
    return sum;
}

我们用正常的思路去写,发现就会超出时间限制,因为这样做 时间复杂度为O(N^2),很显然不符合条件

2. 分析

归并排序(递归)中,可知 ,我们可以通过临时数组tmp 先排序左数组 再排序右数组,最后将左右数组进行排序

而这三种情况,正好对应 逆序对中的 全部从左数组选择、 全部从右数组中选择。 一个选左数组一个选右数组

逆序对的判断

全部从左数组选择、 全部从右数组中选择,我们只需加上返回值即可

统计出某个数后面有多少个数比它小

在归并合并的过程中,可以 得到两个有序的数组,通过有序性快速统计出你逆序对的数量

举例(完整过程解析)

假定left与right数组有序 left=[5,7,9] right=[4,5,8] tmp=[]

第一次循环

left[begin1] (5)>right[begin2] (4) ,将 right[begin2]放入tmp数组中,并将begin2++ 由于是 升序排列, 所以left数组第一个必是最小的数,而这个最小的数比right所取的数大,则right所取的数(4)比left数组中所有数都小,即为tmp进入排序的第一个数 由于4<5,我们要统计 在right数组中有多少数比5小,所以 begin2++

第二次循环

left[begin1] (5) <= right[begin2] (5) 将left[begin1] 放入 tmp数组中 ,并将 begin1++ 最小的数已经放入tmp数组中,此时left[begin1] (5) 就是次小的数 即tmp数组中的第二个数 此时在right数组中 [0,begin2)区间的数 都比left[begin1] (5) 小 即 ret += begin2-0 left[begin1] (5) 已经找到>=它的数,begin1++ 遍历下一个left数组中的数

第三次循环

left[begin1] 1(7) > right [beign2] (5) 将right[begin2] 放入tmp数组中,并将begin2++ 在剩余的数中,由于7>5 ,所以 5就为目前最小的数 ,将其放入 tmp数组中 同时7也没有找到>= 它的数,所以需要 beign2++

第四次循环

left[begin1] (7) < right[begin2] (8) 将left[begin1] 放入tmp数组中,并将begin1++ 在剩余的数中,由于 7<8 ,所以 7就为目前最小的数 ,放入tmp数组中 此时 right数组[0,beign2)区间 小于7 ret+=begin2-0 left[begin1] (7) 已经找到>=它的数,将 begin1++ ,遍历下一个 left数组中的数

第五次循环

left[begin1] (9) > right[begin2] (8) 将right[begin2]放入tmp数组中,并将begin2++ 在剩余的数中,由于 8<9 ,所以 8就为目前最小的数 ,放入tmp数组中 同时begin2++ ,继续寻找right数组中是否存在>=9的数

循环结束的两种存在情况

由于right数组已经遍历完,所以循环停止,再次判断两个数组是否存在数

若 left数组没有走完,则left剩余的每一个数 都 > 原right数组存在的数 right数组区间[0,begin2) 正好为 right数组的所有数 所以还需累加 ret+= begin2-0

若 right数组没有走完,题中要求为逆序对,即左边大于右边的数, 不成立,所以不用统计无意义

3. 正确代码

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
int mergesort1(int* nums, int left, int right, int* tmp)//归并排序
{
    if (left >= right)
    {
        return  0;
    }
    int mid = (left + right) / 2;
    int leftret = mergesort1(nums, left, mid, tmp);//计算左边区间 [left, mid] 中逆序对的数量 = leftRet,并排序;
    int rightret = mergesort1(nums, mid + 1, right, tmp);//. 计算右边区间 [mid + 1, right] 中逆序对的数量 = rightRet,并排序
    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;
    int i = left;
    int voeret = 0;//合并左右两个有序区间,并且计算逆序对的数量
    while (begin1 <= end1 &amp;&amp; begin2 <= end2)
    {
        if (nums[begin1] <= nums[begin2])
        {
            //当 nums[begin1] <= nums[begin2] 时,说明此时右边数组已经遍历过的元素都是比
           // nums[begin1] 小的,因此累加到 voeret 中去
            voeret += begin2 - (mid + 1);//因为计算的begin2刚开始的边界就为 mid+1
            tmp[i++] = nums[begin1++];
        }
        else
        {
            //当 nums[begin1] > nums[begin2] 时,无需统计,直接归并
            tmp[i++] = nums[begin2++];
        }
    }
    //处理归并排序中剩余的元素;
    //当左边有剩余的时候,还需要统计逆序对的数量;
        //当右边还有剩余的时候,无需统计,直接归并。
    while (begin1 <= end1)
    {
        voeret += begin2 - (mid + 1);
        tmp[i++] = nums[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[i++] = nums[begin2++];
    }
    memcpy(nums + left, tmp + left, sizeof(int) * (right - left + 1));
    return leftret + rightret + voeret;//返回 左区间逆序对数量 + 右区间逆序对数量 + 当前合并过程中产生的逆序对数量
}
int  mergesort(int* nums, int numsSize)
{
    int* tmp = (int*)malloc(sizeof(int) * numsSize);//因为我们不想一直malloc创建数组所以在外面开辟
    int ret = mergesort1(nums, 0, numsSize - 1, tmp);
    free(tmp);
    tmp = NULL;
    return ret;
}
int reversePairs(int* nums, int numsSize) {
    return mergesort(nums, numsSize);
}

4.递归展开图

以下标从0到3 的数组进行演示

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-12-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【数据结构】排序算法篇二
任取待排序元素序列中的某元素作为基准值key(把它直接排在它最终要排的那个位置),按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
六点半就起.
2024/10/16
1040
【数据结构】排序算法篇二
【排序算法】 归并排序详解!深入理解!思想+源码实现!
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。 将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
屿小夏
2024/01/22
8070
【排序算法】 归并排序详解!深入理解!思想+源码实现!
数据结构(C语言)之对归并排序的介绍与理解
首先,归并排序可以理解为用分治策略的一种排序算法,这里可以用递归的思想去理解,对一个数组进行不断分割,每次分为两个子数组,直到最后剩下的是一个数据也就是不可再分割,那么就开始对末两个子数组进行归并,然后归回去,在原数组得到有序的数组。(也就是说再每次归并的两个数组一定要是有序的)。
羑悻的小杀马特.
2025/01/23
960
数据结构(C语言)之对归并排序的介绍与理解
【数据结构实战】一起探索快速排序和归并排序的奥秘
上一篇我们讲了各大排序之间的差距,以及他们实现的思路和代码,本期我们将详细的研究一下快速排序和归并排序的奥秘
f狐o狸x
2024/12/24
1000
【数据结构实战】一起探索快速排序和归并排序的奥秘
数据结构从入门到精通——归并排序
归并排序是一种分治策略的排序算法。它将一个序列分为两个等长(几乎等长)的子序列,分别对子序列进行排序,然后将排序结果合并起来,得到完全有序的序列。这个过程递归进行,直到整个序列有序。归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)。
鲜于言悠
2024/03/28
5560
数据结构从入门到精通——归并排序
归并排序含非递归版
至此,归并排序的递归版和非递归版讲解完成,感谢各位友友的来访,祝各位友友前程似锦O(∩_∩)O
大海里的番茄
2024/01/19
1880
归并排序含非递归版
【初阶数据结构】归并排序 - 分而治之的排序魔法
本文讲解的排序算法是归并排序,作为归并算法,其有着快速排序算法没有的特性,也是面试比较常考的算法之一。本文会重点讲解思路以及代码的实现。
埋头编程
2024/10/18
1260
【初阶数据结构】归并排序 - 分而治之的排序魔法
【C语言/数据结构】排序(归并排序|计数排序|排序算法复杂度)
计数排序需要我们新创建一个统计数组,按理来说,数组下标就可以用来当作统计的数,该位置就来存放该数出现的次数。但是,如果要排序的数是从一千多开始的,这样前面的空间就全部浪费了。所以我们采用相对映射的方法。即用待排序的数中,最大的数-最小的数+1就可以得到范围,从而减少空间浪费。接着用原数组的数减去最小值,将该值作为count数组的下标,即相对映射。最后进行排序,记得加回最小值min,这样数据才不会被改变。
秦jh
2024/01/31
1780
【C语言/数据结构】排序(归并排序|计数排序|排序算法复杂度)
【初阶数据结构篇】归并排序和计数排序(总结篇)
gitee 前篇:【初阶数据结构篇】插入、希尔、选择、堆排序介绍 中篇:【初阶数据结构篇】冒泡排序和快速排序
半截诗
2024/10/09
1160
【初阶数据结构篇】归并排序和计数排序(总结篇)
【数据结构与算法】归并排序:从理论到实践的深度剖析
归并排序的非递归实现(也称为迭代实现)主要依赖于循环而非递归调用来分解和合并数组。与递归实现相比,非递归实现避免了递归调用栈的开销,但需要更复杂的索引和边界处理。
倔强的石头_
2024/12/06
3170
【数据结构与算法】归并排序:从理论到实践的深度剖析
数据结构——lesson12排序之归并排序
前面我们学习过六种排序——直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序和快速排序,今天我们就来学习归并排序🥳🎉🎉🎉
大耳朵土土垚
2024/04/04
1590
数据结构——lesson12排序之归并排序
【数据结构算法】归并排序
归并排序(Merge Sort)是建立在归并操作上的一种高效排序算法。该算法是分治法(Divide and Conquer)的典型应用。归并排序的核心思想是将已有序的子序列合并,得到完全有序的序列。
用户11367452
2024/11/21
1090
【数据结构算法】归并排序
【数据结构与算法】:非递归实现快速排序、归并排序
使用栈实现快速排序是对递归版本的模拟。在递归的快速排序中,函数调用栈隐式地保存了每次递归调用的状态。但是在非递归的实现中,你需要显式地使用一个辅助栈来保存子数组的边界
用户11029103
2024/03/19
6620
【数据结构与算法】:非递归实现快速排序、归并排序
八大排序(下)
每一层都会将所有数遍历一遍,所有每一层的时间复杂度为O(N) 一共遍历了高度次 根据二叉树性质:2^h-1=N h=log N 快速排序的整体时间复杂度为O(N*logN)
lovevivi
2022/11/10
2010
八大排序(下)
【初探数据结构】归并排序与计数排序的序曲
本文主要内容是归并的递归和非递归以及计数排序的实现方法。文章会提及很多容易忽视的易错点(大多是我自己踩过的坑😂),这是我在学习这块内容时获取的教训和宝贵经验。
我想吃余
2025/03/31
1110
【初探数据结构】归并排序与计数排序的序曲
归并排序(递归+非递归)
开启掘金成长之旅!这是我参与「掘金日新计划 · 12 月更文挑战」的第9天,点击查看活动详情
lovevivi
2022/12/09
5460
归并排序(递归+非递归)
【数据结构】排序算法系列——归并排序(附源码+图解)
归并排序从字面上来看,它的大致核心应与归并有关——归并拆分开来,变成归类和合并,归类则是将数组进行有序化,合并则是将两个有序的数组进行合并变成一个有序的数组。
Skrrapper
2024/09/25
2630
【数据结构】排序算法系列——归并排序(附源码+图解)
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
        冒泡排序,这个再熟悉不过了,学校中老师讲的第一个排序就是冒泡排序;直接看代码
星辰与你
2024/10/17
1910
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法】归并排序
在MergeSort()函数中,我们首先申请一个临时数组tmp,用于存储排序后的结果,然后我们调用_MergeSort()函数进行排序。_MergeSort()函数会递归地将数组分成两个子数组,并对这两个子数组进行排序和合并,最后,我们释放临时数组tmp
学习起来吧
2024/05/11
1530
【排序算法】归并排序
[数据结构]———归并排序
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤:
小李很执着
2024/06/15
1220
[数据结构]———归并排序
推荐阅读
相关推荐
【数据结构】排序算法篇二
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档