只要写过归并排序的教材十有八九都会在课后题里碰到求逆序对总数这道题。题目本身不复杂含义也很直接在一个数组中统计所有满足前大后小的数对个数。可就是这道题让不少同学从看懂归并排序到能独立写出统计逻辑之间卡了很久。最近我在刷题群看到有人讨论分治(交易逆序对的总数)(6)这个题目点进去一看本质上还是经典的逆序对计数问题只不过包装成了和交易数据挂钩的场景。这篇文章就用一位老开发者的视角从零把这道题拆开为什么暴力解法不行、归并排序为什么天生适合干这件事、代码里最容易踩的坑在哪里以及作为分治思想的同类应用它和分治法求最大元素位置这类题目之间是什么关系。不管你是刚开始学算法的学生还是工作中想补一补基本功的同行认真看完这篇应该都能把逆序对问题彻底吃透。1. 问题到底在问什么先搞清楚逆序对的定义和暴力解法1.1 逆序对的定义与题目本质给定一个长度为 n 的整数数组 nums所谓逆序对就是指满足 i j 且 nums[i] nums[j] 的二元组 (i, j)。换句话说数组里任意两个位置如果前面的数比后面的大这一对就是逆序对。举个例子数组 [3, 5, 2, 1, 4] 中从左往右扫描i0, nums[0]3右侧比 3 小的有 2、1共 2 个i1, nums[1]5右侧比 5 小的有 2、1、4共 3 个i2, nums[2]2右侧比 2 小的有 1共 1 个i3, nums[3]1右侧没有比 1 小的0 个i4, nums[4]4右侧没有元素0 个。总数就是 231 6。这个结果和题目标题里的(6)吻合上了说明这类带编号的题目核心就是算这个总数。题目分治(交易逆序对的总数)里之所以提到交易两个字一般是沿用了力扣或一些题库里的业务包装类似把数组元素想象成某天的价格或交易量统计存在多少历史价格高于当前价格的情况。但底层的数据结构、算法逻辑和传统的逆序对计数完全一致不用被包装迷惑。1.2 为什么暴力解法不可行最容易想到的思路就是双重循环long long countInversionsBruteForce(vectorint nums) { long long cnt 0; int n nums.size(); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (nums[i] nums[j]) cnt; } } return cnt; }这个解法确实是对的但时间复杂度是 O(n^2)。当 n 是 10^5 量级时循环次数大约是 5 × 10^9现代 CPU 每秒大概能执行 10^9 量级的简单操作这意味着单次运行要数秒甚至更久。如果 n 是 10^6那 O(n^2) 无论如何都跑不完属于教科书级别的超时案例。所以这道题的核心考查点就是如何在 O(n log n) 甚至 O(n log n) 以内的时间里数清楚所有逆序对。而分治这个标签直接指向了一个经典解法借助归并排序的合并过程来统计。2. 分治思路为什么归并排序是天然的逆序对计数器2.1 分治三步走分解、解决、合并分治法的通用套路是三步分解把原问题拆成规模更小的子问题解决递归地求解子问题合并把子问题的解组合成原问题的解。对于逆序对问题如果我们把数组从中间切成左右两半那么任意一个逆序对 (i, j) 只会出现在三种位置关系里i 和 j 都在左半部分i 和 j 都在右半部分i 在左半部分j 在右半部分。前两种是子问题交给递归去解决。第三种跨左右两半的情况则需要在合并的阶段统计出来。于是问题就转化成了在合并两个已经有序的子数组时能否顺便高效数出跨区域的逆序对数量。2.2 合并有序数组时如何数逆序对假设我们已经递归处理完左半部分 [left, mid] 和右半部分 [mid1, right]并且左右两边各自都排好序了。现在要用双指针法合并成一个大的有序数组。设置两个指针 i 和 j分别指向左半部分和右半部分的当前元素。合并的过程中如果 nums[i] nums[j]说明左边这个元素不大于右边当前元素它不是逆序对中的前大元素正常拷贝进临时数组i 右移。如果 nums[i] nums[j]说明左边指针指向的元素大于右边指针指向的元素。关键点来了由于左半部分已经有序所以从 i 到 mid 的所有元素也就是左侧还没拷贝的所有元素都大于 nums[j]。也就是说每遇到一次 nums[i] nums[j]就可以直接累加mid - i 1个逆序对而不是一个个去数。这一步是整个算法的灵魂。很多人第一次学的时候卡在这里为什么要加mid - i 1而不是加 1因为左边的数组是有序的nums[i] 是左边剩余元素中最小的一个在合并顺序中它都大于 nums[j] 了那它后面那些更大的元素自然也都大于 nums[j]。这样一次就能统计一批逆序对把本来可能是 O(n^2) 的计数过程压缩到了 O(log n) 层级。从另一个角度理解合并过程本质上是在做跨左右两半的有序归并而每次从右侧取出一个元素时左侧剩余的所有元素都满足前面的大于后面的这些恰好就是跨区域的逆序对。2.3 复杂度为什么是 O(n log n)整个算法的时间复杂度由两部分构成递归深度是 O(log n)每层递归需要把数组完整合并一遍花费 O(n)因此总时间复杂度是 O(n log n)。空间复杂度方面因为需要一份临时数组来辅助合并额外空间是 O(n)。如果刻意优化可以在原数组上做原地归并但实现复杂度太高且常数很大实际工程中没必要标准解法都用临时数组。用一张表对比两种解法解法时间复杂度空间复杂度适用场景暴力双重循环O(n^2)O(1)n 5000 的小数据量调试归并排序分治O(n log n)O(n)n 10^5 的主流场景树状数组/离散化O(n log n)O(n)数据范围大但注重代码短小的时候3. 手写归并排序统计逆序对完整代码与逐段解析3.1 完整可运行的 C 实现下面给出我在实际刷题中使用的模板已经用 long long 处理了溢出问题直接可提交class Solution { public: long long countInversions(vectorint nums) { int n nums.size(); if (n 2) return 0; vectorint temp(n); return mergeCount(nums, temp, 0, n - 1); } private: long long mergeCount(vectorint nums, vectorint temp, int left, int right) { if (left right) return 0; int mid left (right - left) / 2; // 分治先统计左右子数组内部的逆序对 long long cnt 0; cnt mergeCount(nums, temp, left, mid); cnt mergeCount(nums, temp, mid 1, right); // 合并两个有序子数组同时统计跨左右两边的逆序对 int i left; int j mid 1; int k left; while (i mid j right) { if (nums[i] nums[j]) { temp[k] nums[i]; } else { // nums[i] nums[j]说明左侧从 i 到 mid 都大于 nums[j] cnt (mid - i 1); temp[k] nums[j]; } } while (i mid) temp[k] nums[i]; while (j right) temp[k] nums[j]; // 把临时数组的有序结果拷贝回原数组 for (int p left; p right; p) { nums[p] temp[p]; } return cnt; } };如果你用的是 Python核心逻辑完全一样只是把循环改成 Python 风格class Solution: def countInversions(self, nums): n len(nums) if n 2: return 0 temp [0] * n return self._merge_count(nums, temp, 0, n - 1) def _merge_count(self, nums, temp, left, right): if left right: return 0 mid (left right) // 2 cnt 0 cnt self._merge_count(nums, temp, left, mid) cnt self._merge_count(nums, temp, mid 1, right) i, j, k left, mid 1, left while i mid and j right: if nums[i] nums[j]: temp[k] nums[i] i 1 else: cnt (mid - i 1) temp[k] nums[j] j 1 k 1 while i mid: temp[k] nums[i] i 1 k 1 while j right: temp[k] nums[j] j 1 k 1 for p in range(left, right 1): nums[p] temp[p] return cnt3.2 关键细节逐个拆解递归边界条件当left right时区间里只有一个或零个元素不存在逆序对直接返回 0。这个边界要记牢很多新手会写成left right结果在偶数长度的数组测试时也能通过但奇数长度时可能越界反正统一用最稳妥。mid 的计算写成mid left (right - left) / 2而不是(left right) / 2是为了防止 left right 溢出。虽然算法题里 n 一般不会大到让 int 溢出但这个习惯是好的特别是面试时如果被追问答得出来就是加分项。临时数组的作用域我在类里定义了一个成员变量 temp然后在递归中反复使用而不是每次递归都新建一个 vector。这样做的原因是递归深度可以达到 log n 量级每次新建数组会产生大量内存分配拉低性能。实际测试中提前开好 O(n) 的临时数组和每次都开临时数组相比效率差距可能有好几倍。合并时为什么必须拷贝回原数组归并排序的核心操作是把两个有序段合并成一个大有序段而这个大有序段必须存在于原数组的对应区间内下一次递归的上一层合并才能把更大的区间归并起来。如果合并结果只留在临时数组里上层递归就无法感知。所以说先拷贝回原数组这一步不是可选项而是整个算法正确性的保障。计数公式与数据类型cnt (mid - i 1)这个公式的前提是左半部分有序。如果左半部分无序这个公式就是错的所以递归必须先把左右两半各自排好序这是归并排序的天然过程也是这道题能和归并排序结合的原因。逆序对的数量在极端情况下可以达到 n*(n-1)/2当 n 10^5 时这个数接近 5 × 10^9已经超出 int 的表示范围了所以返回值必须用 long long。面试现场如果忘了用 long long在边界测试上直接 WA非常尴尬。3.3 实测验证我用 [3, 5, 2, 1, 4] 手动跑一遍上面的 C 代码第一次递归left0, right4, mid2左侧 [3,5,2]右侧 [1,4]左侧递归left0, right2, mid1左侧 [3,5]右侧 [2][3,5] 递归left0, right1, mid0左侧 [3]右侧 [5]。合并时 35无逆序对返回 0回到 [3,5,2] 的合并左半部分 [3,5]右半部分 [2]。nums[0]3 2cnt (1-01)2即 (3,2) 和 (5,2) 两个逆序对。合并后数组变为 [2,3,5]返回 2右侧 [1,4] 递归left3, right4, mid3左侧 [1]右侧 [4]合并无逆序对返回 0最外层合并左 [2,3,5]右 [1,4]。nums[0]2 1cnt (1-01)2即 (2,1) 和 (3,1) 两个逆序对等等这里要注意此时左半部分是 [2,3,5]mid2i 指向 0 时mid-i1 3-0 3所以 cnt 3对应 (2,1)、(3,1)、(5,1) 三个跨区域逆序对接着 nums[0]2 4拷贝 2然后 j 指向 4但 mid 已经是 2所以左半部分拷贝完最后右半部分 4 拷贝进去。把三层递归的计数加起来0 0 2 0 3 5不对这里的 235但之前手算的真实总数是 6。少了一个我们来仔细核对。原来是我的手动模拟有误。回到 [3,5,2] 的合并左半 [3,5]右半 [2]。nums[0]3 2此时 mid1mid-i1 1-01 2对应 (3,2) 和 (5,2)没错。然后数组变成 [2,3,5]。最外层合并左 [2,3,5]右 [1,4]。i0, j0nums[0]2 1mid2mid-i13对应 (2,1)、(3,1)、(5,1)没问题。此时 cnt235。然后 j 指向 4此时 nums[0]2 4拷贝 2i 指向 3nums[1]3 4拷贝 3i 指向 5nums[2]5 4此时 mid2mid-i1 2-21 1对应 (5,4)这一步被我漏掉了。所以总数 231 6正确。这个手动模拟的过程恰恰说明了代码里最容易漏掉的一种情况当左侧某元素大于右侧当前元素时加的是mid - i 1而 i 在不断变化每次累加的数量可能不是 2 就是 1不能固定用某个常量。初学阶段建议自己用纸笔走一遍流程把每一个计数步骤标出来很快就能理解公式的含义。4. 常见踩坑与排查技巧这些错我全都犯过4.1 merge 过程里的隐藏 bug错误一临时数组索引范围写错很多人会把临时数组的起始索引写成 0而不是 left。例如int k 0; while (i mid j right) { temp[k] ...; }这样当前递归层会把结果写到 temp[0] 开始的位置覆盖了之前递归层写入的数据最后拷贝回原数组时也会错位。正确写法是int k left;。这是最经典的归并排序 bug没有之一。错误二合并结束后忘记拷贝剩余元素只写了一个 while 循环处理两指针相等的情况但没处理 i 或 j 某个先越界后的剩余元素。比如while (i mid j right) { ... } // 遗漏了下面的两个 while while (i mid) temp[k] nums[i]; while (j right) temp[k] nums[j];这样合并出来的数组是残缺的后续递归基于错误的有序数组继续合并结果必然出错。错误三计数公式位置放错如果你把cnt (mid - i 1)写在nums[i] nums[j]的分支里那就把等于的情况也算成了逆序对。逆序对要求严格大于所以相等时必须走左侧拷贝分支不能计数。这个边界容易被忽略尤其是在有重复元素的测试用例中。错误四用 int 接收返回值我上面提到过n10^5 时逆序对数量可能超 int 上限。如果函数签名返回 int在测试用例是降序数组时直接溢出变成负数非常隐蔽。因此养成习惯凡是统计数量且 n 可能超过 10^4 的一律用 long long。4.2 调试技巧如何快速定位归并问题归并排序的递归流程比较抽象肉眼读代码容易漏掉状态变化。我常用的调试方法是设置一个开关打印递归函数的关键变量// 在 mergeCount 入口处取消注释即可打印 // cout left left mid mid right right endl;然后在cnt (mid - i 1)处打印// cout add (mid - i 1) at i i j j endl;这样每次递归都能看到当前区间和累加的逆序对来源配合一个长度为 5 到 8 的乱序小数组手推一遍输出结果就能很快发现是哪一步的区间边界算错了。另外我强烈建议在写完代码后用三种典型用例自测升序数组 [1,2,3,4,5]逆序对为 0降序数组 [5,4,3,2,1]逆序对为 n*(n-1)/2 10有重复元素的数组 [2,2,1,1]逆序对为 4。这三个用例分别覆盖无计数、最大计数、相等元素边界。4.3 性能陷阱临时数组的生命周期前面提到用成员变量提前开好临时数组。但如果你在写递归函数时用的是局部变量vectorint temp(right-left1)每次递归都新建数组那么时间复杂度虽然理论还是 O(n log n)但实际运行会慢很多因为内存分配和释放的次数是 O(log n) 量级每次分配还要初始化常数极大。在力扣这类平台上同样复杂度下有可能因为常数过慢而超时。更好的方式是把 temp 定义在递归入口之外作为类的成员变量或者用引用传递的方式在递归函数间共享。这也是一个典型的空间换时间的取舍提前申请 O(n) 空间换来了递归过程中零分配。5. 同类变体问题与思路扩展一题顶十题5.1 分治法求最大元素的位置热搜词里反复出现分治法求一个n元素数组中最大元素的位置这确实是分治思想的入门第一课把数组分成两半分别求左右两半的最大值位置再比较大小较大者作为整体的最大值位置。代码结构几乎和归并排序一模一样int findMaxPosition(vectorint nums, int left, int right) { if (left right) return left; int mid left (right - left) / 2; int leftMaxPos findMaxPosition(nums, left, mid); int rightMaxPos findMaxPosition(nums, mid 1, right); return nums[leftMaxPos] nums[rightMaxPos] ? leftMaxPos : rightMaxPos; }这个题目和逆序对计数放在一起看能更清晰地理解分治的通用框架递归解决子问题再用 O(1) 或 O(n) 的时间合并结果。区别只在于合并时的操作是比较还是计数。5.2 树状数组解法另一种 O(n log n) 思路虽然题目明确写了分治但如果面试官追问还能怎么做树状数组Fenwick Tree是常见答案。思路是给原数组做离散化把值域压缩到 1 到 n从右往左遍历数组每次查询当前元素值域内已经出现过的、比当前值小的元素个数累加到答案把当前元素的值加入树状数组。具体来说树状数组维护的是值域区间内已出现元素的数量。对于当前元素 xquery(x-1)返回所有已经遍历过的、值小于 x 的元素个数也就是当前元素右侧比它小的元素个数累加即是逆序对总数。这种方法代码稍短但需要理解离散化和树状数组两个前置知识对新手来说分治法的直觉更强。二者的时间复杂度都是 O(n log n)实际运行树状数组常数更小但分治法胜在思路自然而且配合归并排序一起掌握后一举两得。5.3 如果数据不是数组而是链表链表的逆序对计数也可以用分治思路是用快慢指针找中点拆成两条链表分别递归解决左边和右边然后在合并有序链表的阶段统计跨链表的逆序对。核心逻辑和数组一模一样只是合并时是指针操作临时数组也不需要了。这个可以作为进阶练习建议在数组版本熟练后再尝试。5.4 右侧小于当前元素的个数力扣 315 题计算右侧小于当前元素的个数是逆序对问题的变种不是求总数而是要求返回一个数组记录每个元素右侧有多少个元素比它小。用归并排序实现时需要在合并过程中为每个左半元素累加右侧已经被取出的元素个数。即当nums[i] nums[j]时左侧元素 nums[i] 拿下而此时 j - (mid1) 就是右半部分已经合并到前面的、比 nums[i] 小的元素个数把它累加到 count[i] 上。这个变种理解了之后会发现逆序对的本质就是在归并排序的合并过程里左半元素看见了多少个右半元素总数是全局累加单点是局部累加。6. 个人经验总结如何学好这道题这道题是我当初刷算法时量变引起质变的一个转折点。在那之前我对分治的理解停留在递归拆半然后合并的口诀上但真正遇到需要自己想出合并逻辑的题目时经常无从下手。逆序对计数让我第一次体会到分治的难点不在分而在合合并阶段能不能利用子数组的有序性做出高效的统计才是分治算法的精髓所在。如果你正在学习我的建议是不要只看代码一定自己动手推一遍拿一个长度在 5 到 8 之间的数组手写出每一层递归的区间划分一步一步走合并流程用标记记录每次cnt (mid - i 1)具体对应哪几个数对对照最终答案检查是否和暴力解法结果一致反复改代码中的边界条件观察输出变化加深记忆。这样操作下来大概两三个小时就能把归并排序和逆序对问题彻底焊死在脑子里。之后再看右侧小于当前元素的个数翻转对这类题目就会发现都是同一套分治模型换皮不会再感到陌生。最后再分享一个小技巧在实际工程里如果遇到类似的相邻元素间某种统计量的业务需求比如排行榜的逆序程度、相似度排序的错位度、甚至加密算法里的某些变换都可以先想想能不能用归并排序框架来解决。这类分治模型的价值远不止应付一道面试题那么简单。
归并排序解决逆序对问题：分治算法详解与代码实现
只要写过归并排序的教材十有八九都会在课后题里碰到求逆序对总数这道题。题目本身不复杂含义也很直接在一个数组中统计所有满足前大后小的数对个数。可就是这道题让不少同学从看懂归并排序到能独立写出统计逻辑之间卡了很久。最近我在刷题群看到有人讨论分治(交易逆序对的总数)(6)这个题目点进去一看本质上还是经典的逆序对计数问题只不过包装成了和交易数据挂钩的场景。这篇文章就用一位老开发者的视角从零把这道题拆开为什么暴力解法不行、归并排序为什么天生适合干这件事、代码里最容易踩的坑在哪里以及作为分治思想的同类应用它和分治法求最大元素位置这类题目之间是什么关系。不管你是刚开始学算法的学生还是工作中想补一补基本功的同行认真看完这篇应该都能把逆序对问题彻底吃透。1. 问题到底在问什么先搞清楚逆序对的定义和暴力解法1.1 逆序对的定义与题目本质给定一个长度为 n 的整数数组 nums所谓逆序对就是指满足 i j 且 nums[i] nums[j] 的二元组 (i, j)。换句话说数组里任意两个位置如果前面的数比后面的大这一对就是逆序对。举个例子数组 [3, 5, 2, 1, 4] 中从左往右扫描i0, nums[0]3右侧比 3 小的有 2、1共 2 个i1, nums[1]5右侧比 5 小的有 2、1、4共 3 个i2, nums[2]2右侧比 2 小的有 1共 1 个i3, nums[3]1右侧没有比 1 小的0 个i4, nums[4]4右侧没有元素0 个。总数就是 231 6。这个结果和题目标题里的(6)吻合上了说明这类带编号的题目核心就是算这个总数。题目分治(交易逆序对的总数)里之所以提到交易两个字一般是沿用了力扣或一些题库里的业务包装类似把数组元素想象成某天的价格或交易量统计存在多少历史价格高于当前价格的情况。但底层的数据结构、算法逻辑和传统的逆序对计数完全一致不用被包装迷惑。1.2 为什么暴力解法不可行最容易想到的思路就是双重循环long long countInversionsBruteForce(vectorint nums) { long long cnt 0; int n nums.size(); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (nums[i] nums[j]) cnt; } } return cnt; }这个解法确实是对的但时间复杂度是 O(n^2)。当 n 是 10^5 量级时循环次数大约是 5 × 10^9现代 CPU 每秒大概能执行 10^9 量级的简单操作这意味着单次运行要数秒甚至更久。如果 n 是 10^6那 O(n^2) 无论如何都跑不完属于教科书级别的超时案例。所以这道题的核心考查点就是如何在 O(n log n) 甚至 O(n log n) 以内的时间里数清楚所有逆序对。而分治这个标签直接指向了一个经典解法借助归并排序的合并过程来统计。2. 分治思路为什么归并排序是天然的逆序对计数器2.1 分治三步走分解、解决、合并分治法的通用套路是三步分解把原问题拆成规模更小的子问题解决递归地求解子问题合并把子问题的解组合成原问题的解。对于逆序对问题如果我们把数组从中间切成左右两半那么任意一个逆序对 (i, j) 只会出现在三种位置关系里i 和 j 都在左半部分i 和 j 都在右半部分i 在左半部分j 在右半部分。前两种是子问题交给递归去解决。第三种跨左右两半的情况则需要在合并的阶段统计出来。于是问题就转化成了在合并两个已经有序的子数组时能否顺便高效数出跨区域的逆序对数量。2.2 合并有序数组时如何数逆序对假设我们已经递归处理完左半部分 [left, mid] 和右半部分 [mid1, right]并且左右两边各自都排好序了。现在要用双指针法合并成一个大的有序数组。设置两个指针 i 和 j分别指向左半部分和右半部分的当前元素。合并的过程中如果 nums[i] nums[j]说明左边这个元素不大于右边当前元素它不是逆序对中的前大元素正常拷贝进临时数组i 右移。如果 nums[i] nums[j]说明左边指针指向的元素大于右边指针指向的元素。关键点来了由于左半部分已经有序所以从 i 到 mid 的所有元素也就是左侧还没拷贝的所有元素都大于 nums[j]。也就是说每遇到一次 nums[i] nums[j]就可以直接累加mid - i 1个逆序对而不是一个个去数。这一步是整个算法的灵魂。很多人第一次学的时候卡在这里为什么要加mid - i 1而不是加 1因为左边的数组是有序的nums[i] 是左边剩余元素中最小的一个在合并顺序中它都大于 nums[j] 了那它后面那些更大的元素自然也都大于 nums[j]。这样一次就能统计一批逆序对把本来可能是 O(n^2) 的计数过程压缩到了 O(log n) 层级。从另一个角度理解合并过程本质上是在做跨左右两半的有序归并而每次从右侧取出一个元素时左侧剩余的所有元素都满足前面的大于后面的这些恰好就是跨区域的逆序对。2.3 复杂度为什么是 O(n log n)整个算法的时间复杂度由两部分构成递归深度是 O(log n)每层递归需要把数组完整合并一遍花费 O(n)因此总时间复杂度是 O(n log n)。空间复杂度方面因为需要一份临时数组来辅助合并额外空间是 O(n)。如果刻意优化可以在原数组上做原地归并但实现复杂度太高且常数很大实际工程中没必要标准解法都用临时数组。用一张表对比两种解法解法时间复杂度空间复杂度适用场景暴力双重循环O(n^2)O(1)n 5000 的小数据量调试归并排序分治O(n log n)O(n)n 10^5 的主流场景树状数组/离散化O(n log n)O(n)数据范围大但注重代码短小的时候3. 手写归并排序统计逆序对完整代码与逐段解析3.1 完整可运行的 C 实现下面给出我在实际刷题中使用的模板已经用 long long 处理了溢出问题直接可提交class Solution { public: long long countInversions(vectorint nums) { int n nums.size(); if (n 2) return 0; vectorint temp(n); return mergeCount(nums, temp, 0, n - 1); } private: long long mergeCount(vectorint nums, vectorint temp, int left, int right) { if (left right) return 0; int mid left (right - left) / 2; // 分治先统计左右子数组内部的逆序对 long long cnt 0; cnt mergeCount(nums, temp, left, mid); cnt mergeCount(nums, temp, mid 1, right); // 合并两个有序子数组同时统计跨左右两边的逆序对 int i left; int j mid 1; int k left; while (i mid j right) { if (nums[i] nums[j]) { temp[k] nums[i]; } else { // nums[i] nums[j]说明左侧从 i 到 mid 都大于 nums[j] cnt (mid - i 1); temp[k] nums[j]; } } while (i mid) temp[k] nums[i]; while (j right) temp[k] nums[j]; // 把临时数组的有序结果拷贝回原数组 for (int p left; p right; p) { nums[p] temp[p]; } return cnt; } };如果你用的是 Python核心逻辑完全一样只是把循环改成 Python 风格class Solution: def countInversions(self, nums): n len(nums) if n 2: return 0 temp [0] * n return self._merge_count(nums, temp, 0, n - 1) def _merge_count(self, nums, temp, left, right): if left right: return 0 mid (left right) // 2 cnt 0 cnt self._merge_count(nums, temp, left, mid) cnt self._merge_count(nums, temp, mid 1, right) i, j, k left, mid 1, left while i mid and j right: if nums[i] nums[j]: temp[k] nums[i] i 1 else: cnt (mid - i 1) temp[k] nums[j] j 1 k 1 while i mid: temp[k] nums[i] i 1 k 1 while j right: temp[k] nums[j] j 1 k 1 for p in range(left, right 1): nums[p] temp[p] return cnt3.2 关键细节逐个拆解递归边界条件当left right时区间里只有一个或零个元素不存在逆序对直接返回 0。这个边界要记牢很多新手会写成left right结果在偶数长度的数组测试时也能通过但奇数长度时可能越界反正统一用最稳妥。mid 的计算写成mid left (right - left) / 2而不是(left right) / 2是为了防止 left right 溢出。虽然算法题里 n 一般不会大到让 int 溢出但这个习惯是好的特别是面试时如果被追问答得出来就是加分项。临时数组的作用域我在类里定义了一个成员变量 temp然后在递归中反复使用而不是每次递归都新建一个 vector。这样做的原因是递归深度可以达到 log n 量级每次新建数组会产生大量内存分配拉低性能。实际测试中提前开好 O(n) 的临时数组和每次都开临时数组相比效率差距可能有好几倍。合并时为什么必须拷贝回原数组归并排序的核心操作是把两个有序段合并成一个大有序段而这个大有序段必须存在于原数组的对应区间内下一次递归的上一层合并才能把更大的区间归并起来。如果合并结果只留在临时数组里上层递归就无法感知。所以说先拷贝回原数组这一步不是可选项而是整个算法正确性的保障。计数公式与数据类型cnt (mid - i 1)这个公式的前提是左半部分有序。如果左半部分无序这个公式就是错的所以递归必须先把左右两半各自排好序这是归并排序的天然过程也是这道题能和归并排序结合的原因。逆序对的数量在极端情况下可以达到 n*(n-1)/2当 n 10^5 时这个数接近 5 × 10^9已经超出 int 的表示范围了所以返回值必须用 long long。面试现场如果忘了用 long long在边界测试上直接 WA非常尴尬。3.3 实测验证我用 [3, 5, 2, 1, 4] 手动跑一遍上面的 C 代码第一次递归left0, right4, mid2左侧 [3,5,2]右侧 [1,4]左侧递归left0, right2, mid1左侧 [3,5]右侧 [2][3,5] 递归left0, right1, mid0左侧 [3]右侧 [5]。合并时 35无逆序对返回 0回到 [3,5,2] 的合并左半部分 [3,5]右半部分 [2]。nums[0]3 2cnt (1-01)2即 (3,2) 和 (5,2) 两个逆序对。合并后数组变为 [2,3,5]返回 2右侧 [1,4] 递归left3, right4, mid3左侧 [1]右侧 [4]合并无逆序对返回 0最外层合并左 [2,3,5]右 [1,4]。nums[0]2 1cnt (1-01)2即 (2,1) 和 (3,1) 两个逆序对等等这里要注意此时左半部分是 [2,3,5]mid2i 指向 0 时mid-i1 3-0 3所以 cnt 3对应 (2,1)、(3,1)、(5,1) 三个跨区域逆序对接着 nums[0]2 4拷贝 2然后 j 指向 4但 mid 已经是 2所以左半部分拷贝完最后右半部分 4 拷贝进去。把三层递归的计数加起来0 0 2 0 3 5不对这里的 235但之前手算的真实总数是 6。少了一个我们来仔细核对。原来是我的手动模拟有误。回到 [3,5,2] 的合并左半 [3,5]右半 [2]。nums[0]3 2此时 mid1mid-i1 1-01 2对应 (3,2) 和 (5,2)没错。然后数组变成 [2,3,5]。最外层合并左 [2,3,5]右 [1,4]。i0, j0nums[0]2 1mid2mid-i13对应 (2,1)、(3,1)、(5,1)没问题。此时 cnt235。然后 j 指向 4此时 nums[0]2 4拷贝 2i 指向 3nums[1]3 4拷贝 3i 指向 5nums[2]5 4此时 mid2mid-i1 2-21 1对应 (5,4)这一步被我漏掉了。所以总数 231 6正确。这个手动模拟的过程恰恰说明了代码里最容易漏掉的一种情况当左侧某元素大于右侧当前元素时加的是mid - i 1而 i 在不断变化每次累加的数量可能不是 2 就是 1不能固定用某个常量。初学阶段建议自己用纸笔走一遍流程把每一个计数步骤标出来很快就能理解公式的含义。4. 常见踩坑与排查技巧这些错我全都犯过4.1 merge 过程里的隐藏 bug错误一临时数组索引范围写错很多人会把临时数组的起始索引写成 0而不是 left。例如int k 0; while (i mid j right) { temp[k] ...; }这样当前递归层会把结果写到 temp[0] 开始的位置覆盖了之前递归层写入的数据最后拷贝回原数组时也会错位。正确写法是int k left;。这是最经典的归并排序 bug没有之一。错误二合并结束后忘记拷贝剩余元素只写了一个 while 循环处理两指针相等的情况但没处理 i 或 j 某个先越界后的剩余元素。比如while (i mid j right) { ... } // 遗漏了下面的两个 while while (i mid) temp[k] nums[i]; while (j right) temp[k] nums[j];这样合并出来的数组是残缺的后续递归基于错误的有序数组继续合并结果必然出错。错误三计数公式位置放错如果你把cnt (mid - i 1)写在nums[i] nums[j]的分支里那就把等于的情况也算成了逆序对。逆序对要求严格大于所以相等时必须走左侧拷贝分支不能计数。这个边界容易被忽略尤其是在有重复元素的测试用例中。错误四用 int 接收返回值我上面提到过n10^5 时逆序对数量可能超 int 上限。如果函数签名返回 int在测试用例是降序数组时直接溢出变成负数非常隐蔽。因此养成习惯凡是统计数量且 n 可能超过 10^4 的一律用 long long。4.2 调试技巧如何快速定位归并问题归并排序的递归流程比较抽象肉眼读代码容易漏掉状态变化。我常用的调试方法是设置一个开关打印递归函数的关键变量// 在 mergeCount 入口处取消注释即可打印 // cout left left mid mid right right endl;然后在cnt (mid - i 1)处打印// cout add (mid - i 1) at i i j j endl;这样每次递归都能看到当前区间和累加的逆序对来源配合一个长度为 5 到 8 的乱序小数组手推一遍输出结果就能很快发现是哪一步的区间边界算错了。另外我强烈建议在写完代码后用三种典型用例自测升序数组 [1,2,3,4,5]逆序对为 0降序数组 [5,4,3,2,1]逆序对为 n*(n-1)/2 10有重复元素的数组 [2,2,1,1]逆序对为 4。这三个用例分别覆盖无计数、最大计数、相等元素边界。4.3 性能陷阱临时数组的生命周期前面提到用成员变量提前开好临时数组。但如果你在写递归函数时用的是局部变量vectorint temp(right-left1)每次递归都新建数组那么时间复杂度虽然理论还是 O(n log n)但实际运行会慢很多因为内存分配和释放的次数是 O(log n) 量级每次分配还要初始化常数极大。在力扣这类平台上同样复杂度下有可能因为常数过慢而超时。更好的方式是把 temp 定义在递归入口之外作为类的成员变量或者用引用传递的方式在递归函数间共享。这也是一个典型的空间换时间的取舍提前申请 O(n) 空间换来了递归过程中零分配。5. 同类变体问题与思路扩展一题顶十题5.1 分治法求最大元素的位置热搜词里反复出现分治法求一个n元素数组中最大元素的位置这确实是分治思想的入门第一课把数组分成两半分别求左右两半的最大值位置再比较大小较大者作为整体的最大值位置。代码结构几乎和归并排序一模一样int findMaxPosition(vectorint nums, int left, int right) { if (left right) return left; int mid left (right - left) / 2; int leftMaxPos findMaxPosition(nums, left, mid); int rightMaxPos findMaxPosition(nums, mid 1, right); return nums[leftMaxPos] nums[rightMaxPos] ? leftMaxPos : rightMaxPos; }这个题目和逆序对计数放在一起看能更清晰地理解分治的通用框架递归解决子问题再用 O(1) 或 O(n) 的时间合并结果。区别只在于合并时的操作是比较还是计数。5.2 树状数组解法另一种 O(n log n) 思路虽然题目明确写了分治但如果面试官追问还能怎么做树状数组Fenwick Tree是常见答案。思路是给原数组做离散化把值域压缩到 1 到 n从右往左遍历数组每次查询当前元素值域内已经出现过的、比当前值小的元素个数累加到答案把当前元素的值加入树状数组。具体来说树状数组维护的是值域区间内已出现元素的数量。对于当前元素 xquery(x-1)返回所有已经遍历过的、值小于 x 的元素个数也就是当前元素右侧比它小的元素个数累加即是逆序对总数。这种方法代码稍短但需要理解离散化和树状数组两个前置知识对新手来说分治法的直觉更强。二者的时间复杂度都是 O(n log n)实际运行树状数组常数更小但分治法胜在思路自然而且配合归并排序一起掌握后一举两得。5.3 如果数据不是数组而是链表链表的逆序对计数也可以用分治思路是用快慢指针找中点拆成两条链表分别递归解决左边和右边然后在合并有序链表的阶段统计跨链表的逆序对。核心逻辑和数组一模一样只是合并时是指针操作临时数组也不需要了。这个可以作为进阶练习建议在数组版本熟练后再尝试。5.4 右侧小于当前元素的个数力扣 315 题计算右侧小于当前元素的个数是逆序对问题的变种不是求总数而是要求返回一个数组记录每个元素右侧有多少个元素比它小。用归并排序实现时需要在合并过程中为每个左半元素累加右侧已经被取出的元素个数。即当nums[i] nums[j]时左侧元素 nums[i] 拿下而此时 j - (mid1) 就是右半部分已经合并到前面的、比 nums[i] 小的元素个数把它累加到 count[i] 上。这个变种理解了之后会发现逆序对的本质就是在归并排序的合并过程里左半元素看见了多少个右半元素总数是全局累加单点是局部累加。6. 个人经验总结如何学好这道题这道题是我当初刷算法时量变引起质变的一个转折点。在那之前我对分治的理解停留在递归拆半然后合并的口诀上但真正遇到需要自己想出合并逻辑的题目时经常无从下手。逆序对计数让我第一次体会到分治的难点不在分而在合合并阶段能不能利用子数组的有序性做出高效的统计才是分治算法的精髓所在。如果你正在学习我的建议是不要只看代码一定自己动手推一遍拿一个长度在 5 到 8 之间的数组手写出每一层递归的区间划分一步一步走合并流程用标记记录每次cnt (mid - i 1)具体对应哪几个数对对照最终答案检查是否和暴力解法结果一致反复改代码中的边界条件观察输出变化加深记忆。这样操作下来大概两三个小时就能把归并排序和逆序对问题彻底焊死在脑子里。之后再看右侧小于当前元素的个数翻转对这类题目就会发现都是同一套分治模型换皮不会再感到陌生。最后再分享一个小技巧在实际工程里如果遇到类似的相邻元素间某种统计量的业务需求比如排行榜的逆序程度、相似度排序的错位度、甚至加密算法里的某些变换都可以先想想能不能用归并排序框架来解决。这类分治模型的价值远不止应付一道面试题那么简单。
