教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载本文是 InterviewGuide 仓库《带你快速刷完67道剑指offer》专栏中 No35 题「数组中的逆序对」的完整技术解析。文章以原文档为主体完整继承题目描述、数据范围、取模要求与多版 C 解法并结合仓库内「十大排序-归并排序」源码深入讲解分治统计原理、三种归并变体的实现差异与易错点帮助读者真正掌握这一类「归并类」题目的通解套路直击校招与社招手撕算法考点。题目背景与出处本题出自《剑指 Offer》原书与牛客网《剑指offer》专题专栏序号 No35并在力扣上有对应题目「剑指 Offer 51. 数组中的逆序对」。原文档所在的刷题专栏docs/notes/03-hunting_job/03-algorithm/02-sword-offer/01-introduce.md说明所有题目均来自于《何海涛. 剑指 Offer[M]. 电子工业出版社, 2012.》一书题目顺序与牛客网保持一致每道题都汇集了牛客网与力扣网上的精妙解法。题目描述在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组求出这个数组中的逆序对的总数 P并将 P 对 1000000007 取模的结果输出即输出P % 1000000007。输入描述与数据范围题目保证输入的数组中没有相同的数字数据范围如下数据规模size 上限50% 的数据size 10^475% 的数据size 10^5100% 的数据size 2*10^5数据范围是本题选型的关键信号当 size 达到 2*10^5 时O(n²) 的双重循环算法会超时必须采用 O(n log n) 级别的解法归并排序或树状数组。示例输入1,2,3,4,5,6,7,0输出7解释除 0 以外的每个数字都大于 0且 0 位于数组末尾因此共形成 7 个逆序对。力扣版示例为输入: [7,5,6,4] 输出: 5逆序对为(7,5)、(7,6)、(7,4)、(5,4)、(6,4)共 5 对。解法一只通过 50% 的笨方法O(n²) 暴力统计原文档给出的第一版解法思路非常直观从数组尾部向前遍历对每个元素data[i]统计其右侧所有小于它的元素个数累加即得逆序对总数。int InversePairs(vectorint data) { if (data.size() 1) return 0; int len data.size(); vectorint dp(len, 0); for (int i len - 2; i 0; --i) { for (int j i 1; j len; j) { if (data[i] data[j]) { dp[i]; } } } return accumulate(dp.begin(), dp.end(), 0) % 1000000007; }复杂度与缺陷两层循环的时间复杂度为 O(n²)。原文档明确标注该方法「只通过 50%」即仅能应付 size 10^4 的数据规模一旦数据量增长到 10^5、2*10^5就会超时。这版代码的价值在于帮助读者建立「逆序对」的朴素认知作为后续归并解法的对照基准。解法二基于归并排序的经典做法从尾端合并计数核心思路借归并排序统计逆序对原文档给出的核心解法是在归并排序「合并」两个有序子数组的过程中顺带统计逆序对数量。归并排序本身是分治法Divide and Conquer的典型应用仓库中的归并排序专题docs/notes/03-hunting_job/03-algorithm/01-basic-algorithm/02-06-十大排序.md对其原理做了如下说明将一个大的无序数组有序可以把大的数组分成两个然后对这两个数组分别进行排序之后再把这个数组合并成一个有序的数组。通过递归的方式将大的数组一直分割直到数组的大小为 1此时只有一个元素那么该数组就是有序的了之后再把两个数组大小为 1 的合并成一个大小为 2 的再把两个大小为 2 的合并成 4 的……直到全部小的数组合并起来。逆序对统计正是借助这一「两个有序子数组合并」的过程当左边子数组的某个元素大于右边子数组的某个元素时由于两个子数组内部都已有序左边子数组中从该元素起一直到分界点 mid 的所有元素都大于右边的这个元素因此可以一次性累加多个逆序对从而把统计代价从逐个比较降到 O(n log n)。原文档解法从尾端开始比较原文档的第一版归并解法从数组尾端开始比较将较大的元素写入辅助数组尾部同时完成计数int InversePairs(vectorint data) { if (data.size() 0) return 0; vectorint copy(data); // 辅助数组每次递归后有序 return InversePairsCore(data, copy, 0, data.size() - 1); } int InversePairsCore(vectorint data, vectorint copy, int begin, int end) { if (begin end) return 0; int mid begin (end - begin) / 2; int left InversePairsCore(copy, data, begin, mid); // 这里的一步很绝减少了一次交换/赋值 int right InversePairsCore(copy, data, mid 1, end); int end1 mid; // 左半段从尾端开始 int end2 end; // 右半段从尾端开始 int index_copy end; // 结果写入辅助数组尾端 long res 0; // 归并排序相当于两个有序数组合成一个有序表从尾端开始是为了计数 while (begin end1 mid 1 end2) { if (data[end1] data[end2]) { copy[index_copy--] data[end1--]; res end2 - mid; // 右半段 [mid1, end2] 共 end2-mid 个元素都小于 data[end1] res % 1000000007; } else copy[index_copy--] data[end2--]; } while (begin end1) copy[index_copy--] data[end1--]; while (mid 1 end2) copy[index_copy--] data[end2--]; return (left right res) % 1000000007; }原文档对这段代码的评价是InversePairsCore(copy, data, begin, mid)中 copy 和 data 互换位置好评……这样就减少了赋值的那一步了。这里解释一下这个「绝妙的一步」常规归并排序在每层递归合并后需要把辅助数组的内容复制回原数组才能保证上一层递归读到的是有序序列本解法在递归调用时把copy与data的角色互换上一层把合并结果写入copy下一层就把copy当数据源、把data当写入目标。这样每次递归结束后有序结果天然落在下一次合并要读取的数组上省去了每次合并后的回写复制仓库归并排序专题中的「节约时间的一种递归归并排序」一节也记载了同样的技巧见 02-06-十大排序.md并特别提醒千万注意不要把 copy 和 nums 赋值反了。取模方面由于 n 最大为 2*10^5最坏情况下逆序对总数约为 n(n-1)/2 ≈ 2*10^10已超出 32 位 int 的表示范围因此代码用long res累加并在每次累加后立即res % 1000000007防止中间结果溢出。解法三从小到大的归并写法更符合直觉1、二刷版本正序合并 右侧计数原文档的二刷记录给出了从头部开始、归并成从小到大的有序序列的写法逻辑更贴近常规归并排序因此「这种方法更好理解一些」int InversePairsCore(vectorint data, vectorint copy, int begin, int end) { if (begin end) return 0; int mid begin (end - begin) / 2; int low1 begin, high1 mid, low2 mid 1, high2 end; int left InversePairsCore(copy, data, low1, high1); // copy 与 data 互换省去回写 int right InversePairsCore(copy, data, low2, high2); long res 0; int copyIndex low1; // 归并排序相当于两个有序数组合成一个有序表 while (low1 high1 low2 high2) { if (data[low1] data[low2]) { copy[copyIndex] data[low1]; res high2 - low2 1; // data[low1] data[low2]则 [low1, high1] 中从 low1 到 mid 的元素都大于 data[low2] res % 1000000007; } else copy[copyIndex] data[low2]; } while (low1 high1) copy[copyIndex] data[low1]; while (low2 high2) copy[copyIndex] data[low2]; return (left right res) % 1000000007; } int InversePairs(vectorint data) { if (data.size() 0) return 0; vectorint copy(data); // 辅助数组每次递归后有序 return InversePairsCore(data, copy, 0, data.size() - 1); }这一版本的计数点在data[low1] data[low2]分支此时从low1开始到high1的所有元素都大于data[low2]因为左右两个子数组都已各自有序一次累加high2 - low2 1个逆序对。原文档特别注释了1 的易错点——区间[low2, high2]的元素个数是high2 - low2 1如果漏掉 1计数会偏少例如 low20、high23 时实际有 4 个元素。2、三刷版本data[low1] data[low2]分支计数原文档还记录了另一种对称写法在「左边元素小于右边元素」时直接归并左边元素否则即data[low1] data[low2]在归并右边元素时累加high1 - low1 1。两种写法本质等价区别只在于「在哪个分支里完成计数」int InversePairsCore(vectorint data, vectorint copy, int begin, int end) { if (begin end) return 0; int mid begin (end - begin) / 2; int low1 begin, high1 mid, low2 mid 1, high2 end; int left InversePairsCore(copy, data, low1, high1); int right InversePairsCore(copy, data, low2, high2); long res 0; int copyIndex low1; // 下面就开始两两进行比较若前面的数大于后面的数就构成逆序对 while (low1 high1 low2 high2) { if (data[low1] data[low2]) { copy[copyIndex] data[low1]; } else { // data[low1] data[low2] copy[copyIndex] data[low2]; res high1 - low1 1; // [low1, high1] 区间内所有元素都大于 data[low2] res % 1000000007; } } while (low1 high1) copy[copyIndex] data[low1]; while (low2 high2) copy[copyIndex] data[low2]; return (left right res) % 1000000007; } 原文档记录该版本的实测表现为「运行时间 78ms、占用内存 5788k」牛客网环境下可作为性能参考。 ## 解法四力扣「剑指 Offer 51」的 C 题解 力扣版题目剑指 Offer 51. 数组中的逆序对与牛客版相比数据规模与边界略有差异原文档给出的限制与实测如下 0 数组长度 50000 - 执行用时244 ms击败 97.32% 的 C 提交 - 内存消耗44.4 MB击败 100.00% 的 C 提交 对应的 AC 代码 ~~~cpp int reversePairsCore(vectorint nums, vectorint copy, int begin, int end) { if (begin end) return 0; // 终止条件 int mid begin (end - begin) / 2; int low1 begin, high1 mid, low2 mid 1, high2 end; int leftRes reversePairsCore(copy, nums, low1, high1); int rightRes reversePairsCore(copy, nums, low2, high2); int copyIndex low1, res 0; while (low1 high1 low2 high2) { if (nums[low1] nums[low2]) { // 这里需要保持绝对的小 copy[copyIndex] nums[low1]; } else { res high1 - low1 1; // [low1, high1] 此时都是大于 nums[low2] 的 // 千万注意要 1因为 high1 - low1 会少一个如 high13, low10 时是 4 个数 copy[copyIndex] nums[low2]; } } while (low1 high1) copy[copyIndex] nums[low1]; while (low2 high2) copy[copyIndex] nums[low2]; return res leftRes rightRes; } int reversePairs(vectorint nums) { if (nums.size() 1) return 0; vectorint copy(nums); return reversePairsCore(nums, copy, 0, nums.size() - 1); }与牛客版的关键差异比较符号是力扣版不保证数组元素互不相同因此当nums[low1] nums[low2]时两者不构成逆序对逆序对要求「前面大于后面」必须走「归并左边元素」的分支即注释中强调的「这里需要保持绝对的小」递归终止条件为begin end多了一层防御空区间直接返回 0无需取模力扣版返回原始逆序对总数不要求对 1000000007 取模。复杂度分析与「互换数组」技巧总结版本时间复杂度空间复杂度适用数据范围暴力双重循环O(n²)O(n)dp 数组size 10^4只能过 50% 用例归并排序统计O(n log n)O(n)辅助数组 copysize 2*10^5可通过 100% 用例三种归并写法的共同点与易错点分治计数原理逆序对总数 左半段内部逆序对 右半段内部逆序对 跨左右两段的逆序对正好与归并排序「先分后合」的过程天然对应区间计数 1无论是high2 - low2 1还是high1 - low1 1统计的是闭区间元素个数务必 1互换数组省回写递归传参时把data与copy互换省去每层合并后的回写复制是本题实现上的点睛之笔仓库归并排序专题同样记录了这一技巧取模防溢出牛客版要求输出P % 1000000007累加中间结果用long并及时取模注意重复元素若题目不保证元素互异如力扣版比较时用保持稳定性避免把相等元素误计为逆序对。归并类题目的延伸力扣 315 / 327 / 493原文档在题末特别标注了归并类题目的延伸清单力扣 315. 计算右侧小于当前元素的个数力扣 327. 区间和的个数力扣 493. 翻转对这三道题与本题同属「归并类」题目它们都在归并排序的合并过程中借助「左右子数组各自有序」的性质用 O(1) 的区间长度计算代替逐个比较从而将整体复杂度控制在 O(n log n)。建议读者在吃透本题的三种归并写法后按这个清单逐题练习即可系统掌握归并分治思想在计数类问题上的通解套路。在 InterviewGuide 仓库中的定位与后续学习路径本篇文章对应仓库中 35-剑指offer.md属于《带你快速刷完67道剑指offer》专栏专栏导读。据仓库算法模块食用指南01-introduce.md的建议算法小白、时间充裕先系统刷《带你快速刷完67道剑指offer》专栏再刷《精选力扣300道算法题》临时抱佛脚、临近秋招认真刷完剑指offer专栏后突击《面试高频算法真题》归并排序基础可先阅读仓库「十大排序」中的归并排序专题02-06-十大排序.md其中包含迭代版、递归版、vector 递归版、省回写优化版等多种 C 实现与本题解法互为印证。面试手撕算法时逆序对是考察「分治思想 归并排序底层理解」的高频题能写出 O(n log n) 解法并讲清「为什么合并时能批量计数」「为什么辅助数组要互换角色」往往比单纯 AC 更能体现算法功底。赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐剑指 Offer 数组中的逆序对No35四种解法带你吃透归并排序计数思想剑指 Offer 数组中的逆序对No35四种解法带你吃透归并排序计数思想 本文基于 InterviewGuide 仓库中《带你快速刷完67道剑指offer文档教程知识库剑指 Offer 51基于归并排序的数组逆序对统计剑指 Offer 51 数组中的逆序对剑指 Offer 51基于归并排序的数组逆序对统计剑指 Offer 51 数组中的逆序对 本文围绕《剑指 Offer》第 51 题「数组中的逆序对」展开示例工程CS-Notes 剑指 Offer 51 详解用归并排序 O(n log n) 统计数组中的逆序对CS Notes 剑指 Offer 51 详解用归并排序 O n log n 统计数组中的逆序对 本文基于 CS Notes 仓库中的 51. 数组中的逆序对知识库文档教程上一篇LLMBox 开源项目教程下一篇BM25S 开源项目教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考