CS-Notes 剑指 Offer 51 详解：用归并排序 O(n log n) 统计数组中的逆序对-北京尧图网络

CS-Notes 剑指 Offer 51 详解用归并排序 O(n log n) 统计数组中的逆序对【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本文基于 CS-Notes 仓库中的 51. 数组中的逆序对题解展开完整讲解逆序对问题的定义、暴力解法的瓶颈以及如何借助归并排序的合并过程在一次 O(n log n) 的排序中同步完成计数。读完后你将掌握排序中顺手统计的分治计数思想、计数语句cnt m - i 1的推导逻辑以及辅助数组声明位置、等值元素处理、取模输出等工程细节并能在算法 - 排序一文的归并排序实现之间做出对照理解。一、题目定义题目描述引自 51. 数组中的逆序对在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组求出这个数组中的逆序对的总数。用下标语言精确描述对于数组nums若i j且nums[i] nums[j]则(i, j)构成一个逆序对目标是统计满足条件的下标对总数。注意两个边界定义用的是严格大于相等元素nums[i] nums[j]不构成逆序对逆序对按下标对计数而非按值计数两个位置上的重复大数也会分别计数。以经典例子nums [7, 5, 6, 4]为例逆序对为 (7,5)、(7,6)、(7,4)、(5,4)、(6,4)共 5 个完全递增的数组逆序对为 0完全递减的长度为 n 的数组逆序对为 n(n-1)/2这也提示了答案的规模可能达到 O(n²) 量级。二、暴力解法及其瓶颈最直接的做法是双重循环枚举所有i j的下标对并逐一比较大小public int InversePairsBrute(int[] nums) { long cnt 0; for (int i 0; i nums.length; i) { for (int j i 1; j nums.length; j) { if (nums[i] nums[j]) { cnt; } } } return (int) (cnt % 1000000007); }时间复杂度为 O(n²)。当 n 达到 10⁴~10⁵ 量级时10⁸~10¹⁰ 次比较已不可接受。而本题的关键观察是逆序对本质上是无序程度的度量——它等价于把数组排序过程中有多少对元素需要跨过彼此。归并排序恰好会在合并两个有序子数组时暴露出这种跨越多半区的元素对因此可以在 O(n log n) 的排序过程中免费地完成统计。三、归并排序计数完整解法下面完整给出原题解与 51. 数组中的逆序对中的 Java 代码一致并在每一段做注解private long cnt 0; private int[] tmp; // 在这里声明辅助数组而不是在 merge() 递归函数中声明 public int InversePairs(int[] nums) { tmp new int[nums.length]; mergeSort(nums, 0, nums.length - 1); return (int) (cnt % 1000000007); } private void mergeSort(int[] nums, int l, int h) { if (h - l 1) return; int m l (h - l) / 2; mergeSort(nums, l, m); mergeSort(nums, m 1, h); merge(nums, l, m, h); } private void merge(int[] nums, int l, int m, int h) { int i l, j m 1, k l; while (i m || j h) { if (i m) tmp[k] nums[j]; else if (j h) tmp[k] nums[i]; else if (nums[i] nums[j]) tmp[k] nums[i]; else { tmp[k] nums[j]; this.cnt m - i 1; // nums[i] nums[j]说明 nums[i...mid] 都大于 nums[j] } k; } for (k l; k h; k) nums[k] tmp[k]; }调用方式InversePairs(new int[]{7, 5, 6, 4})返回 5。1. 为什么辅助数组声明在类成员位置代码注释中特意强调在这里声明辅助数组而不是在 merge() 递归函数中声明。归并排序自顶向下递归的深度为 log n每次merge()若都new一个临时数组将引入 O(n log n) 次的分配开销且每次分配的总长度之和也是 O(n log n)。将tmp提升为类成员并在入口处只分配一次使额外的总内存开销降为 O(n)这是该类实现反复出现的性能惯例。2. 计数语句cnt m - i 1的推导这是整道题目解的灵魂。合并阶段的不变式是左半区nums[l..m]和右半区nums[m1..h]此刻都已经是有序的。当循环走到else分支即nums[i] nums[j]时nums[j]是右半区当前尚未取出的最小元素由于左半区有序nums[i..m]是左半区中所有 nums[i]的元素必然都严格大于nums[j]于是nums[j]与i, i1, ..., m这m - i 1个下标分别构成一个逆序对一次比较即可完成m - i 1次计数。整个统计过程恰好发生在标准的归并比较路径上不引入任何额外的比较因此总时间仍是 O(n log n)。3.比较的细节相等元素不计数合并时先比较nums[i] nums[j]相等时优先取左半区元素不计入逆序对。这与题目前面一个数字大于后面的数字的严格定义一致。顺带地这一写法保证了归并的稳定性左半区元素优先与算法 - 排序中归并方法先取左边保证稳定性的注释是同一约定。4. 回写方式tmp 与 nums 下标对齐实现中tmp直接以l..h的下标写入而不是从 0 开始合并完成后用一段拷贝nums[k] tmp[k]写回原数组。这与算法 - 排序中的实现方向相反——那里是先把nums[k]复制到aux[k]再从aux取数写回nums本解法则是先写tmp再拷回nums。两种方向都只是借助等长辅助数组完成双指针归并的两种写法空间都是 O(n)效果等价。5. 取模输出与计数变量类型cnt声明为long递减数组长度为 n 时逆序对数可达 n(n-1)/2int 在 n 较大时会溢出返回值(int) (cnt % 1000000007)在线题目原题解文档中附牛客题目链接要求结果对 1000000007 取模因此只在最终输出时做一次取模即可——统计过程中cnt保持真实值不影响比较逻辑。6. 递归结构与复杂度终止条件if (h - l 1) return;区间长度小于 2单元素或空区间时天然有序直接返回。对空数组调用时mergeSort(nums, 0, -1)会命中该条件函数安全返回划分点int m l (h - l) / 2;用差值减半而非(l h) / 2避免下标求和溢出的隐患每次merge对当前区间做线性扫描合并所有层的总工作量为 T(n) 2T(n/2) O(n)由主定理得时间 O(n log n)额外空间 O(n)。7. 手工推演[7, 5, 6, 4]递归到底后先合并[7, 5]i0, j17 5走 else 分支cnt 1(7,5)得到[5, 7]再合并[6, 4]cnt 1(6,4)得到[4, 6]最后合并[5, 7]与[4, 6]7 4且5 4时nums[j]4对左半区 i0 处取数cnt m - i 1 2(5,4)、(7,4)之后6 5走 elsecnt 1(6,5)。累计 cnt 1 1 2 1 5与枚举结果一致最终tmp回写后原数组被排成[4, 5, 6, 7]这也说明该方法会就地排序原数组介意的调用方需先拷贝。四、可扩展的替代思路除归并外逆序对还有一类 O(n log n) 的经典做法从右向左扫描用树状数组BIT维护已扫描过的、小于当前值的元素个数等价于查询比它小且位于它右边的元素有多少。两种方式复杂度相同归并法实现更短、与本题解仓库风格一致适合面试现场手写BIT 法在值域离散化后需要在线查询的场景下更通用。此处仅作方向性提示完整实现可参照本仓库 Leetcode 题解 - 二分查找、Leetcode 题解 - 双指针等章节的分治与扫描技巧自行练习。五、小结逆序对问题在 O(n log n) 排序中顺手统计跨半区元素对核心是合并阶段cnt m - i 1的批量计数工程细节三处辅助数组tmp只分配一次、保证相等元素不计数且合并稳定、long计数加最终取模 1000000007复杂度 O(n log n) 时间 / O(n) 空间且会就地打乱排好序原数组延伸阅读算法 - 排序的归并排序合并方法、自顶向下/自底向上两种写法提供了归并过程的通用参考剑指 Offer 题解 - 目录中本题被归入排序分类可与同类的第 45 题把数组排成最小的数自定义比较器对照练习排序思想在面试中的不同变形。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

CS-Notes 剑指 Offer 51 详解：用归并排序 O(n log n) 统计数组中的逆序对

相关推荐

从图鉴到图网络：基于宝可梦栖息地的相遇网络构建与分析实战

ECC 的 TypeScript/JavaScript 编码风格规则：从不可变性与 Zod 校验到 Hook 自动检测

单臂路由实验详解：VLAN间路由、802.1Q封装与子接口配置实战

更多资讯

如何高效使用Komikku：从新手到专家的完整指南

探索Hermes Agent的计算机视觉模型集成：CNN、Transformer与生成模型

Hermes Agent 大模型部署实战：量化、推理加速与显存优化的组合拳

终极实战：为Hermes Agent构建专业级监控告警体系

Hermes Agent容器化部署实战指南：从零到生产级配置

企业级AI代理部署实战：Hermes Agent容器化架构深度解析

今日更新

AI辅助技术栈评估：提升研发决策效率60%

从生成Token到直接决策：Jev如何重塑AI Agent工程实践

32G统一内存跑大模型：内存账、TPS实测与端云分流

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？