欢迎阅读愿旖旎· 个人主页学习专栏《算法专栏》《LangChain学习》《贪心算法》 钱塘江上潮信来今日方知我是我✨当前学习内容《归并排序》一.题目LCR 170. 交易逆序对的总数 - 力扣LeetCode 欢迎来到「交易逆序对的总数」题解之旅本文将带你从统计一串交易里有多少对前面比后面大的组合这一直观场景出发深入理解归并排序 合并时计数的巧妙运用并掌握如何在双指针合并的瞬间累加跨段逆序对来在 O(n log n) 内统计全部逆序对。在开始之前建议你先了解题目背景这是 LCR 170 题给定整数数组record统计满足i j且record[i] record[j]的逆序对总数。本质上暴力两两比较是 O(n²)而归并排序在合并两个有序段时能一次算出大量跨段逆序对问题转化为分治过程中的计数。明确学习目标掌握归并排序的计数时机理解ret mid - cur1 1的推导并熟练处理相等元素与跨层不重复计数等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如record [7,5,6,4]输出5。本文将从问题转化、分治拆分、合并计数、边界防护到代码实现层层递进。即使你对逆序对还不熟悉我们也会从两段都排好序后右段一个元素能一次性抵消左段好几个这一直觉出发让你轻松抓住核心思想——分治拆分合并时一次清账。现在让我们一起归并计数数出所有逆序对吧 二、算法分析1. 问题分析前置分析题目要求统计数组record中满足i j且record[i] record[j]的逆序对总数。关键约束n可达5×10⁴暴力 O(n²) 会超时逆序对要求严格大于相等不算结果可能很大。核心思路归并排序在合并两个各自有序的段时只要右段某个元素比左段当前元素小就能确认左段剩余的所有元素都比它大从而一次性累加多个逆序对——总代价 O(n log n)。 例子为什么暴力不可行record [7,5,6,4]暴力要比较C(4,2) 6对n 5×10⁴时约1.25×10⁹ 次比较必超时而归并排序只在合并时扫一遍两段就能把跨段的逆序对全部数出来本例共 5 对75、76、74、54、64总比较次数只有 O(n log n) 级别。2. 算法策略归并排序 合并时计数核心步骤递归拆分取中点mid left (right - left) / 2分别处理[left, mid]与[mid1, right]。递归终止if (left right) return;单元素无逆序对。升序合并cur1指左段、cur2指右段每次取较小者写入tmp。计数时机当record[cur1] record[cur2]取右段元素时左段剩余[cur1, mid]全部大于它累加ret mid - cur1 1。收尾搬运某段耗尽后把另一段剩余元素搬入tmp不计数。回填record[i] tmp[i - left]返回本层合并结果。 示例record [7,5,6,4]逆序对总数 5阶段区间比较操作ret 增量合并[0,1]7 vs 57 5取 511-01合并[2,3]6 vs 46 4取 412-21合并[0,3]5 vs 45 4取 421-015、7 都大合并[0,3]5 vs 65 ≤ 6取 50合并[0,3]7 vs 67 6取 611-11收尾——搬入 70三次计数分别在[0,1]、[2,3]、[0,3]层累加1 1 3 5✅与手工枚举的 5 对一致。3. 正确性说明计数公式正确合并时左段[left, mid]已经升序若record[cur1] record[cur2]则record[cur1..mid]每个都大于record[cur2]单调性且它们的下标都小于cur2因此恰好全部构成逆序对个数为mid - cur1 1。跨层不重复每层合并只统计左段元素与右段元素之间的逆序对段内部的逆序对已在递归的子层统计过互不重叠。收尾不计数剩余元素被整体搬运时不可能产生新的跨段逆序对否则它早就被取出了所以收尾阶段只需搬运、无需累加。相等不算时取左段元素不累加保证严格大于才计入符合逆序对定义。 例子为什么mid - cur1 1恰好是逆序对数合并[5,7]与[4,6]取出4时左段剩余[5,7]都大于4下标也都小于4的位置于是54、74恰好两对个数mid - cur1 1 1 - 0 1 2——公式直接来自左段剩余长度无需逐个枚举。4. 实现细节初始化tmp作为成员变量、ret 0为成员累加器跨递归层累计tmp.resize(n)一次分配。边界防护if (left right) return;单元素无逆序对mid left (right - left) / 2防溢出tmp[i - left]回填时偏移必须减 leftret用int即可n 5×10⁴时逆序对最多约1.25×10⁹未超2^31。复杂度时间 O(n log n)log n 层合并每层总扫描 O(n)空间 O(n)tmpO(log n)递归栈。关键操作ret mid - cur1 1;取右段元素时累加跨段逆序对、if (record[cur1] record[cur2]) tmp[i] record[cur1];相等取左不计数。 例子相等元素如何被正确处理record [2,2,1]合并[2,2]与[1]时2 1→ret mid - cur1 1 1 - 0 1 2即两个2各与1构成逆序对而两个2相等前面的2不构成与后面2的逆序对。最终ret 2✅——让相等的两个元素互不计入但都算作大于更小元素的逆序对。5. 返回值返回ret逆序对的总数在合并过程中逐层累加完成对应题目返回逆序对总数。三.代码class Solution { vectorint tmp; // 辅助数组所有合并轮次复用只分配一次 int ret 0; // 逆序对总数跨递归层累计 public: int reversePairs(vectorint record) { int n record.size(); tmp.resize(n); // 一次性开好避免每次递归都分配 mergeSort(record, 0, n - 1); // 对闭区间 [0, n-1] 归并并计数 return ret; } void mergeSort(vectorint record, int left, int right) { // 1. 递归终止单元素无逆序对 if (left right) { return; } // 2. 取中点分别排序左右两段 int mid left (right - left) / 2; mergeSort(record, left, mid); mergeSort(record, mid 1, right); // 3. 升序合并并在“取右段元素”时统计跨段逆序对 int cur1 left; // 左段指针 int cur2 mid 1; // 右段指针 int i 0; // tmp 写入位置 while (cur1 mid cur2 right) { if (record[cur1] record[cur2]) // 相等取左段不构成逆序对 { tmp[i] record[cur1]; } else { // 左段 [cur1, mid] 全部大于 record[cur2]共 mid - cur1 1 个 ret mid - cur1 1; tmp[i] record[cur2]; } } // 4. 收尾剩余元素直接搬运不产生新的逆序对 while (cur1 mid) { tmp[i] record[cur1]; } while (cur2 right) { tmp[i] record[cur2]; } // 5. 回填tmp 从 0 写起故 record[left k] 对应 tmp[k] for (int k left; k right; k) { record[k] tmp[k - left]; } } };四、易错点分析难点1计数公式mid - cur1 1的含义ret mid - cur1 1;合并时左段[left, mid]已升序若record[cur1] record[cur2]则record[cur1..mid]每个都大于record[cur2]且下标都更小因此恰好都是逆序对个数就是剩余的mid - cur1 1。这个公式依赖左段有序——若左段无序就无法保证剩余元素都更大公式失效。这是归并统计逆序对的核心依据。难点2计数必须发生在取右段元素时else { ret mid - cur1 1; // 只在取右段时累加 tmp[i] record[cur2]; }逆序对要求i j且record[i] record[j]——只有右段元素更小时才存在左段在前、右段在后且更大的关系。若在取左段元素时累加if分支就变成找比它大的右段元素方向反了若两个分支都加会重复计数。计数的时机与合并方向强绑定写错一个分支结果就全错。难点3与决定相等元素是否被误算if (record[cur1] record[cur2])逆序对定义是严格大于相等不构成逆序对。用时相等取左段、不累加正确若写成相等时会走else分支累加mid - cur1 1把相等的元素误算为逆序对结果偏大。一个符号之差答案就错——这是本题最隐蔽的陷阱之一。难点4跨层不重复计数mergeSort(record, left, mid); // 先统计段内 mergeSort(record, mid 1, right); ret mid - cur1 1; // 再统计跨段每层合并只统计左段元素 × 右段元素的逆序对段内部的逆序对在递归子层已经统计完毕两层不会重复。若在合并时试图把段内元素也重新数一遍就会重复累加。理解分治的每一层各管一段关系才不会数错。五、流程图 闭幕 恭喜你完成了「交易逆序对的总数」问题的学习为了巩固知识并进一步拓展建议你 动手实践在 LeetCode 上提交代码尝试不同的测试用例。 深入思考本题在归并排序的合并阶段统计逆序对。请问为什么左段剩余元素全部大于右段当前元素这一性质能让我们一次算出多个逆序对计数公式是ret mid - cur1 1。请问这个公式由什么推出如果左段不是有序的还能用吗代码只在取右段元素时累加。请问在取左段元素时累加会得到什么两个分支都累加又会怎样代码用record[cur1] record[cur2]。请问改成会发生什么逆序对的定义对此有何要求如果你觉得本文对你有所帮助欢迎 点赞 / 收藏 关注作者获取更多题解 留言交流你的疑问或优化思路 深入思考答案因为左段[left, mid]已经升序若record[cur1] record[cur2]则左段从cur1到mid的每个元素都大于record[cur2]且下标全部更小这些全部都是逆序对个数即剩余长度mid - cur1 1。公式来自左段剩余长度cur1已扫过的元素已被取出不再参与剩下的[cur1, mid]个数就是mid - cur1 1。它强依赖左段有序——无序时剩余元素不一定都大于当前右段元素公式就不成立。取左段元素时累加方向就反了变成统计比当前左段元素更大的右段元素与i j且record[i] record[j]不符两个分支都加则同一对会被计算两次结果翻倍。会让相等元素走累加分支把相等误算成逆序对逆序对要求严格大于所以必须用取左段、相等不计数。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨
企业数字化 ERP 产品动态
相关推荐
网络原理入门必看(一)------LAN,WAN,IP地址,端口号,协议,网络通信五元组 网络原理入门必看(一)------LAN,WAN,IP地址,端口号,协议,网络通信五元组 文章摘要:本文介绍了学习网络原理的基础元素:LAN,WAN,IP地址,端口号,协议,网络通信五元素. 目录
1.局域网LAN和广域网WAN
2.网络通信基础(IP地址,端口号)
3.协议
4.五元组
正文
1.局域网LAN和广域网… · 2026/11/4 15:24:54
实验2:基于TuGraph的Epinions电商信任网络图查询与图算法分析 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/5 0:48:29
OpenStack 认证管理:角色、用户、组、项目、配额,五样东西到底谁绑谁 在 Horizon 里点「创建用户」,对话框要求填项目和角色;在命令行里 openstack role add 又要 --project --user 两个参数。这两处其实在说同一件事:OpenStack 里没有任何「直接给用户一个权限」的操作,权限永远是「某个角色&#x… · 2026/11/14 8:54:15
电工证丢了怎么补办?国家级初级电工证图片+上岗必备全攻略 电工证丢了怎么补办?国家级初级电工证图片+上岗必备全攻略 你是不是也遇到过这种情况:手头正急着上岗,结果一翻证件,国家级初级电工证图片找不到了,心里直打鼓?别慌,这事儿咱们今天就掰扯清楚, 上岗必备… · 2026/11/19 3:31:43
哪个电工证有用模拟考试题库 低压电工证有用吗?学历不高也能考!全国通用证书怎么选 你是不是也经常听说“哪个电工证有用”,但又不知道从哪下手?特别是学历不高,担心自己连报名资格都没有,根本不敢去打听。其实,低压电工证是全国通用的,只要你符合基本条件,不管学历高低,都可以… · 2026/11/19 3:31:43
湖北长阳电工证哪里考,真实经历告诉你怎么过实操考试 湖北长阳电工证哪里考,真实经历告诉你怎么过实操考试 实操考试心里没底怕挂科,这事儿我懂,我自己就是从商丘转岗过来的,当时考电工证时手都抖。现在回过头来看,其实只要准备到位、方法对了,就没那么可怕。今天就把我在湖北长阳考电工证的真实经历和干货… · 2026/11/19 3:31:43
阎良低压电工证考试值不值得考?过期了千万别拖 阎良低压电工证考试值不值得考?过期了千万别拖 证书过期了不知道怎么复审延期,这种情况在很多从业人员中并不罕见。尤其是像低压电工证这种高频使用、操作性强的特种作业证书,一旦过期,轻则影响工作,重则可能带来法律风险。阎良低压电工证考试,作为电工… · 2026/11/19 3:31:43
周宁电工证哪里考 电工证在哪考别交冤枉钱 周宁电工证哪里考 电工证在哪考别交冤枉钱 怕考不过白交培训费?周宁电工证在哪考,这事儿真不能马虎。你要是正打算报名电工证,但又担心培训机构坑你、考试难度大,那这篇内容就是为你量身定制的。… · 2026/11/19 3:31:43
附近的低压电工证报考避坑指南:郑州在职建筑工人怎么考才不吃亏 附近的低压电工证报考避坑指南:郑州在职建筑工人怎么考才不吃亏 你是不是也遇到过这样的情况: 不知道去哪报名怕被中介坑 ,好不容易找到个报名点,结果要么收费高得离谱,要么干脆不给办证?这年头, 附近的低压电工证… · 2026/11/19 3:30:43
长春初级电工证怎么考?通过率揭秘全在这里 长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/18 8:19:55
国内电工证报考条件与考试时间 低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/18 8:19:53
电工作业时如何断电?电子证书到底能不能全国通用? 电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/18 14:38:14
姑苏区哪里考电工证好考前押题怎么找 姑苏区哪里考电工证好考前押题怎么找 工地太忙根本没时间复习考试,电工证考前还总找不到靠谱的 考前押题 资源,真让人头疼。如果你也是在苏州姑苏区从事建筑或电力行业的,那这些建议你一定要看完。 为什么姑苏区考电工证的人这么多?… · 2026/11/19 0:00:12
罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南 罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南 之前考的证在外省能不能转过来?这几乎是每个特种作业证书持有者都会遇到的问题,特别是像你这样已经在外地工作多年,想回老家罗定发展或者重新规划职业路径的人。别急,今天就给你一条清晰的路… · 2026/11/19 0:00:12
罗定能考电工证吗 电工证含金量到底有多少? 罗定能考电工证吗 电工证含金量到底有多少? 之前考的证在外省能不能转过来,这几乎是每个准备考电工证的朋友最先想到的问题。特别是在罗定这样的地方,很多人的电工证都是在外地考的,现在想在当地继续使用,但不知道怎么办。实际上,电工证的 含金量… · 2026/11/19 0:00:12
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/17 21:47:42
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/17 21:47:42
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/19 0:22:38