1. 题目到底在考什么别被交易两个字带偏先把这个题目本身说清楚。分治(交易逆序对的总数)(6)我第一眼看到这行字的时候也愣了一下什么交易什么总数其实这就是一道很经典的逆序对统计题只不过在不同平台、不同题单里换了个马甲。你去翻剑指Offer它叫数组中的逆序对去LeetCode搜是LCR 170. 交易逆序对的总数在牛客或者洛谷可能就叫求逆序对。名字怎么换都无所谓核心问题只有一个给定一个长度为 n 的数组 nums计算出有多少对下标 (i, j) 满足 i j且 nums[i] nums[j]最后把总数返回。注意交易这两个字纯粹是题面包装——可能是某些平台把数组想象成交易记录的价格序列逆序对就是后一天价格低于前一天的情况去掉了包装底子还是那个逆序对。我见过不少人在评论区被这种包装搞得一脸懵以为是什么区块链、金融风控的题目其实完全不是。那为什么这个题值得单独拿出来写一份而且还要专门强调分治因为它是面试高频题更是分治思想的一个绝佳样本。你说暴力也能做两层循环 i 从 0 到 nj 从 i1 到 n判断条件累加思路三分钟就能写出来。但一旦 n 到 10^5 甚至 10^6 的规模O(n^2) 的算法跑起来就是灾难。我看过不少初学者拿暴力代码去提交大数据直接超时心态瞬间崩掉。所以这个题真正的考点是你能不能从暴力 O(n^2) 的思路里跳出来用 O(n log n) 的分治法在排序的副产物中把逆序对数出来。顺带说一句题目里括号还有个(6)这种编号通常表示这是某个专题训练里的第 6 题比如分治专题的第六道题。这说明出题人希望你练习的就是分治这一块。包括热词里那些分治法求一个n元素数组中最大元素的位置、四边形不等式优化dp 分治解法都是同一个专题下不同的问题——它们都在反复锤炼一个能力把大问题拆成小问题解决小问题再合并结果。逆序对归并排序的写法正是这个能力的集中体现。2. 归并排序统计逆序对的底层原理一次合并批量清算2.1 先复习一下归并排序本身的拆与合归并排序是分治思想的经典代言人。整个流程就两步拆把数组从中间劈开分成左右两半然后递归地继续劈直到每个子数组只有一个元素。一个元素当然是有序的不需要排序。合从最小子问题开始向上回溯把两个已经有序的左右子数组合并成一个更大的有序数组。合并过程用双指针i 指向左半部分开头j 指向右半部分开头比较 nums[i] 和 nums[j]小的放进临时数组然后对应指针后移。哪边先走完就把剩下的一股脑拷贝进临时数组最后把临时数组的内容覆盖回原数组对应区间。代码框架大概是下面这样void mergeSort(vectorint nums, int l, int r) { if (l r) return; int mid l (r - l) / 2; mergeSort(nums, l, mid); mergeSort(nums, mid 1, r); merge(nums, l, mid, r); }但如果你只是把归并排序写出来这道题只能拿一半的分数——排序本身并不直接告诉你逆序对的数量你得在合的过程里做文章。这里就是逆序对问题的精髓所在。2.2 合并时的一次巧合才发现逆序对可以批量结算先说结论逆序对的数量可以在合并两个有序数组的时候顺手统计出来不需要额外扫描。关键点在于递归到某层时左右两个子数组内部都已经有序这是归并排序的性质。假设左半部分叫 L右半部分叫 R它们分别有序。那么任意一个 L 中的元素和 R 中的元素它们之间的相对大小关系恰好能反映跨左右两部分的逆序对数量。具体规则如果 L[i] R[j]说明 L[i] 比当前 R[j] 小它不会和 R[j] 构成逆序对i 后移。如果 L[i] R[j]那说明 L[i] 比 R[j] 大而且因为 L 是有序的L[i] 后面所有元素也都比 L[i] 大自然也都比 R[j] 大。于是从 i 到 L 的末尾这一整段全部和 R[j] 构成逆序对——一次就统计出一批逆序对数量是 L长度减去 i 的位置。你看明白这个逻辑的巧妙之处了吗在暴力解法里一个 R[j] 要和左边所有比它大的元素分别比较但在归并排序里因为 L 已经有序一旦发现 L[i] R[j]就能确定 L[i]、L[i1]……L[mid] 全都大于 R[j]然后一口气累加 mid - i 1 个数。单次比较引发的统计量从1变成了一堆这就是 O(n log n) 的来源。2.3 手算一遍数组 [7, 5, 6, 4] 的完整推演光说理论容易飘我拿一个经典小数组走一遍完整流程。假设 nums [7, 5, 6, 4]。第一层拆mid 1左半边 [7, 5]右半边 [6, 4]。左半边再拆[7] 和 [5]各自只有一个元素不用再拆。合并 [7] 和 [5]左指针在 7右指针在 5。7 5所以 7 这一整个左区间只有一个元素都和 5 构成逆序对累加 1。合并结果是 [5, 7]。右半边同理[6] 和 [4]6 4累加 1。合并结果是 [4, 6]。回到顶层合并 [5, 7] 和 [4, 6]左指针指向 5右指针指向 4。5 4左区间从 5 开始到末尾 [5, 7] 都大于 4累加 2。右指针移到 6。5 6左指针右移到 7。7 6左区间从 7 到末尾 [7] 都大于 6累加 1。右指针移到末尾左区间还剩 [7]全部拷贝。三次合并共累加 1 1 2 1 5。验证一下原数组 [7, 5, 6, 4] 的逆序对(7,5)、(7,6)、(7,4)、(5,4)、(6,4)确实是 5 对一个不多一个不少。注意顶层合并时一次累加 2 的效果——这就是批量结算的直观感受。2.4 为什么这个算法是 O(n log n) 而不是 O(n^2)归并排序每一层合并的总工作量是 O(n)因为每一层的所有区间加在一起恰好覆盖整个数组长度 n而数组被递归拆分成 log n 层每次折半。所以总复杂度 O(n log n)。相比暴力的 O(n^2)当 n 10^5 时暴力要比较大约 10^10 次归并排序只要大约 10^5 × 17 次差距接近六个数量级。这也是为什么所有高效逆序对解法都离不开分治或者树状数组这类低复杂度框架——不是技巧炫技是数据规模逼着你必须这么做。3. 代码落地C 和 Python 两版实现的关键差异3.1 C 版注意临时数组的作用域和引用传递C 写这个题最稳妥的姿势是直接在递归函数内部维护一个临时数组或者作为成员变量复用。我推荐在类里开一个全局的 temp 数组避免每次递归都 vector 拷贝导致额外的 O(n log n) 内存开销和拷贝耗时。核心代码直接给出来class Solution { private: vectorint temp; long long mergeCount(vectorint nums, int l, int r) { if (l r) return 0; int mid l (r - l) / 2; long long cnt 0; cnt mergeCount(nums, l, mid); cnt mergeCount(nums, mid 1, r); int i l, j mid 1, p 0; while (i mid j r) { if (nums[i] nums[j]) { temp[p] nums[i]; } else { cnt mid - i 1; // 关键批量累加 temp[p] nums[j]; } } while (i mid) temp[p] nums[i]; while (j r) temp[p] nums[j]; for (i l, p 0; i r; i, p) { nums[i] temp[p]; } return cnt; } public: long long reversePairs(vectorint record) { temp.resize(record.size()); return mergeCount(record, 0, record.size() - 1); } };注意我用了 long long 作为返回类型这个细节下面专门说。还有递归函数里cnt mergeCount(...)这两个递归调用必须写在合并前还是合并后没区别因为左右两侧内部的逆序对已经在它们的合并阶段统计完了我们只需要保证顶层合并前左右各自有序即可。顺序不影响正确性。3.2 Python 版优雅但注意递归深度Python 写分治通常比 C 松弛一些但有两个坑必须提前规避一是temp列表的传递方式二是递归深度。class Solution: def reversePairs(self, record: List[int]) - int: nums record n len(nums) temp [0] * n def merge_sort(l: int, r: int) - int: if l r: return 0 mid (l r) // 2 cnt merge_sort(l, mid) merge_sort(mid 1, r) i, j, p l, mid 1, l while i mid and j r: if nums[i] nums[j]: temp[p] nums[i] i 1 else: cnt mid - i 1 temp[p] nums[j] j 1 p 1 while i mid: temp[p] nums[i] i 1 p 1 while j r: temp[p] nums[j] j 1 p 1 for k in range(l, r 1): nums[k] temp[k] return cnt return merge_sort(0, n - 1)Python 里temp直接闭包引用外层的 list不需要重新赋值。递归深度要注意当 n 很大时Python 默认递归深度是 1000归并排序递归深度是 log n约 17~20所以纯递归没问题。但如果你把递归改成 while 模拟或者某些极端写法里递归深度变成 O(n)就会碰 RecursionError。归并排序天然深度 O(log n)所以这点其实很安全。3.3 为什么合并时必须做稳定排序式的 判断代码里用的是if nums[i] nums[j]注意这里的等号。有人会问改成严格小于nums[i] nums[j]行不行分情况讨论。如果是求逆序对题目定义是 nums[i] nums[j] 才算一对相等不算。那么合并时如果左指针的值等于右指针的值应该让左指针先走即 nums[i] nums[j] 时走左指针这样相等元素不会被误判为逆序对。这是稳定性的要求也决定了排序后相等元素相对顺序不变。如果你把判断条件改成严格小于一旦相等元素出现右指针可能先走导致它被错误地统计进逆序对里。我当初第一次写的时候就用错了条件结果测试数组 [1, 2, 1, 1] 一直多算两对排查了很久才意识到是等于号的问题。这个细节虽然一行但足以让整道题全错。4. 边界问题、取模陷阱与调试心得4.1 数据范围为什么逼你用 long long逆序对的最大数量是 C(n, 2) n × (n-1) / 2。如果 n 10^5最大逆序对数大约是 5 × 10^9远超 int 的 2^31 - 1约 2.1 × 10^9。所以只要你用 int 存结果在最坏情况数组严格降序下必然溢出提交就会得到莫名其妙的错误答案。我的建议是不管题目数据范围写没写一律用 long long。30 位以内够用吗如果 n 是 10^9 量级long long 也扛不住但那种规模通常不会用归并排序硬做。工程上long long 是逆序对题型的默认安全选择。C 里注意mid - i 1这个表达式的类型i 和 mid 是 int但它们参与累加时编译器会自动提升到 long long所以只要 cnt 是 long long 就没问题。Python 读者倒是不用担心溢出——Python 的 int 是任意精度。但 C 就得老老实实写对类型这是初学者最容易忽略又最致命的地方。4.2 取模要求的处理不是最后取一次就完事有些版本的题目要求返回结果对 1000000007 取模比如某些大厂笔试题变体。这时候有个坑不能只在 return 前取模。因为在递归中途cnt 可能已经越过 int 甚至 long long 的范围导致提前溢出最后取模也救不回来。正确做法有两种整个 cnt 都全程用 long long中途不做任何取模只在最终 return 前取模。这要求 n 不太大long long 能全程装下最大值。如果 n 特别大比如 10^6 以上在累加时每加一次就取一次模也就是cnt (cnt mid - i 1) % MOD。但千万注意第二种做法里返回值本身是取模后的而取模后的 cnt 再参与递归统计是安全的因为逆序对数量只做加法取模满足加法交换律和结合律。不过有个问题如果中途取模递归排序时的比较大小判断不受影响因为排序只关心元素值不关心计数。所以两种做法正确性都没问题区别是性能每步取模有一点点额外开销但可以接受。我个人的经验是能不取模就不取模肝语言特性题时但如果题面写了取模简化起见还是在累加的同时每一步用cnt (cnt ...) % MOD省得最后忘了。4.3 合并边界最容易翻车的地方递归出口是 l r不是 l r。因为某些写法 mid 计算可能让区间划分出问题虽然归并排序通常不会导致 l r但二手习惯任何递归都写成if (l r) return;更安全。循环条件while (i mid j r)里的等号必须写。漏掉等号会导致左右区间剩余元素没有被处理完虽然排序结果可能还是对的因为后面有两个 while 兜底但对逆序对统计来说漏掉的元素可能是逆序对——尤其在右指针 j 走完后左指针剩余元素不会额外产生新的逆序对因为在前面循环里该统计的已经统计完了。如果你漏了等号导致提前跳出前面循环少执行了一次该在循环里统计的逆序对可能刚好漏掉。还有 mid 的计算要用l (r - l) / 2不要用(l r) / 2。虽然对普通小数组这俩没区别但 l r 在极端边界r 接近 INT_MAX时可能溢出养成本能性写前者能避免很多潜在 bug。这种看起来等价但实际有坑的细节最容易在面试手撕代码时翻车。4.4 对数器验证别急着提交先暴力对拍写算法题我发现最有效的自检不是静态读代码而是写一个暴力解法和自己的高效解法做对拍。随机生成小数组长度 1 到 10元素数值范围 -100 到 100各跑 1000 次比较两种结果是否一致。对拍器代码很简单我通常直接在主函数里跑随机测试bool test() { Solution s; for (int t 0; t 1000; t) { int n rand() % 10 1; vectorint a(n); for (int i 0; i n; i) a[i] rand() % 201 - 100; vectorint b a; int ans1 s.reversePairs(a); int ans2 0; for (int i 0; i n; i) for (int j i 1; j n; j) if (b[i] b[j]) ans2; if (ans1 ! ans2) return false; } return true; }这个对拍器几乎能抓住 90% 以上的边界问题负数、相等元素、空数组、单元素数组全都能测到。我第一次写逆序对的时候就是靠它发现条件错误的。真的强烈建议每个人都养成这个习惯尤其是分治、递归这类容易小边界出错的题型。5. 从逆序对看分治思维相关变体与工程启发5.1 同源问题分治法求数组最大元素的位置热词里的分治法求一个n元素数组中最大元素的位置和逆序对是同一个专题的两道兄弟题。思路也是拆成左右两边分别求左边最大值的位置和右边最大值的位置再比较两个最大值谁更大谁就是全数组最大值。代码核心长这样int findMaxPos(vectorint nums, int l, int r) { if (l r) return l; int mid l (r - l) / 2; int leftPos findMaxPos(nums, l, mid); int rightPos findMaxPos(nums, mid 1, r); return nums[leftPos] nums[rightPos] ? leftPos : rightPos; }这个题很直白地展示了分治的最小化思想先递归到单元素再在每层合并时比较并选出胜者。和逆序对的区别在于最大元素位置在合并时只需要常数次比较而逆序对在合并时利用有序性做了批量统计。但两者的递归骨架完全同源你先学会其中一个另一个几乎就是顺手的事。5.2 树状数组解法另一种统计逆序对的思路分治不是唯一解法。逆序对还能用树状数组Fenwick Tree做原理是离散化 顺序扫描 前缀查询。大致思路把数组元素离散化成排名然后从左往右扫描每遇到一个元素就查询已经扫描过的元素里比它大的数量然后把它自己加进树状数组。这里查询和修改都是 O(log n)总复杂度同样是 O(n log n)。两种解法怎么选归并排序版不依赖离散化适合直接处理而且分治思想更容易在面试中现场讲清楚树状数组版代码更短大约 20 行但引入离散化和树状数组两个额外概念如果面试官让你现场证明正确性解释成本更高。我一般建议面试首选归并排序因为写法天然和分治专题契合工程或比赛里如果对线段树、树状数组更熟用树状数组成熟度更高。别贪多先把归并排序版本写到肌肉记忆级别。5.3 变体翻转对LeetCode 493另一个常见变体是 LeetCode 493 翻转对统计 i j 且 nums[i] 2 * nums[j] 的对数。归并排序同样适用但注意合并时不能直接在排序比较里统计——因为条件带了一个 2 倍关系你不能只在nums[i] nums[j]的分支里顺手统计。处理方式是在合并前对左区间依次查找右区间中有多少元素满足 nums[i] 2 * nums[j]也就是一个额外的双指针扫描然后再做正常的合并排序。这个变体进一步说明归并排序的框架是灵活的真正难点在于统计什么、在哪个阶段统计。5.4 工程上的启发合并阶段的增量信息从逆序对这个题里我最想分享的一点是分治不是单纯把问题拆开再拼回去而是要在合并阶段捕捉那些只有合并才能看清的增量信息。暴力的逆序对统计为什么会慢因为它每一次比较都是孤立的没有任何信息可以被复用。归并排序之所以快是因为排序让左右区间的内部结构变得有序于是某个右元素比多少个左元素小这个问题从一个一个数变成了左区间剩余长度这个 O(1) 的结论。本质上排序产生的有序性就是一种可以被复用的数据预处理信息。我在实际工作里其实不太会手写归并排序——大多数语言自带 sort。但分治思想本身到处都有git merge 的过程是分治合并SQL 的归并连接是分治外排分布式系统里 MapReduce 的 shuffle 阶段也是大排序拆成小排序再合并。搞懂逆序对这一道题你不仅刷了一道算法题还理解了一个非常底层的计算机思维模式先让局部有序再让局部之间的比较变得廉价。5.5 给初学者的刷题路径建议如果你刚接触分治我建议按这个顺序训练先写归并排序本身不要统计任何东西纯排序跑通。在纯归并排序的合并函数里加上cnt mid - i 1这一行跑逆序对题。跑完这道题换分治法求最大元素位置这类简单题体会拆解 比较的骨架。再挑战翻转对体会合并前额外统计的变化。每一步都要配对数器随机验证。很多初学者卡在这道题是卡在为什么排序能统计逆序对这个思维转换上。我的建议是别光看题解自己拿几张纸按第 2 节那样手推数组 [7, 5, 6, 4] 的完整递归树把每一层合并产生的累加数写在旁边。你亲手推一遍比看十遍题解都管用。逆序对这道题看起来小但它把分治、归并、稳定性、数据范围、边界条件这些要素全串在了一起。把它彻底吃透你后面在面试里遇到任何排序变体的题目都会比没刷过的人多一层底气。
分治算法详解：归并排序统计逆序对的高效解法
1. 题目到底在考什么别被交易两个字带偏先把这个题目本身说清楚。分治(交易逆序对的总数)(6)我第一眼看到这行字的时候也愣了一下什么交易什么总数其实这就是一道很经典的逆序对统计题只不过在不同平台、不同题单里换了个马甲。你去翻剑指Offer它叫数组中的逆序对去LeetCode搜是LCR 170. 交易逆序对的总数在牛客或者洛谷可能就叫求逆序对。名字怎么换都无所谓核心问题只有一个给定一个长度为 n 的数组 nums计算出有多少对下标 (i, j) 满足 i j且 nums[i] nums[j]最后把总数返回。注意交易这两个字纯粹是题面包装——可能是某些平台把数组想象成交易记录的价格序列逆序对就是后一天价格低于前一天的情况去掉了包装底子还是那个逆序对。我见过不少人在评论区被这种包装搞得一脸懵以为是什么区块链、金融风控的题目其实完全不是。那为什么这个题值得单独拿出来写一份而且还要专门强调分治因为它是面试高频题更是分治思想的一个绝佳样本。你说暴力也能做两层循环 i 从 0 到 nj 从 i1 到 n判断条件累加思路三分钟就能写出来。但一旦 n 到 10^5 甚至 10^6 的规模O(n^2) 的算法跑起来就是灾难。我看过不少初学者拿暴力代码去提交大数据直接超时心态瞬间崩掉。所以这个题真正的考点是你能不能从暴力 O(n^2) 的思路里跳出来用 O(n log n) 的分治法在排序的副产物中把逆序对数出来。顺带说一句题目里括号还有个(6)这种编号通常表示这是某个专题训练里的第 6 题比如分治专题的第六道题。这说明出题人希望你练习的就是分治这一块。包括热词里那些分治法求一个n元素数组中最大元素的位置、四边形不等式优化dp 分治解法都是同一个专题下不同的问题——它们都在反复锤炼一个能力把大问题拆成小问题解决小问题再合并结果。逆序对归并排序的写法正是这个能力的集中体现。2. 归并排序统计逆序对的底层原理一次合并批量清算2.1 先复习一下归并排序本身的拆与合归并排序是分治思想的经典代言人。整个流程就两步拆把数组从中间劈开分成左右两半然后递归地继续劈直到每个子数组只有一个元素。一个元素当然是有序的不需要排序。合从最小子问题开始向上回溯把两个已经有序的左右子数组合并成一个更大的有序数组。合并过程用双指针i 指向左半部分开头j 指向右半部分开头比较 nums[i] 和 nums[j]小的放进临时数组然后对应指针后移。哪边先走完就把剩下的一股脑拷贝进临时数组最后把临时数组的内容覆盖回原数组对应区间。代码框架大概是下面这样void mergeSort(vectorint nums, int l, int r) { if (l r) return; int mid l (r - l) / 2; mergeSort(nums, l, mid); mergeSort(nums, mid 1, r); merge(nums, l, mid, r); }但如果你只是把归并排序写出来这道题只能拿一半的分数——排序本身并不直接告诉你逆序对的数量你得在合的过程里做文章。这里就是逆序对问题的精髓所在。2.2 合并时的一次巧合才发现逆序对可以批量结算先说结论逆序对的数量可以在合并两个有序数组的时候顺手统计出来不需要额外扫描。关键点在于递归到某层时左右两个子数组内部都已经有序这是归并排序的性质。假设左半部分叫 L右半部分叫 R它们分别有序。那么任意一个 L 中的元素和 R 中的元素它们之间的相对大小关系恰好能反映跨左右两部分的逆序对数量。具体规则如果 L[i] R[j]说明 L[i] 比当前 R[j] 小它不会和 R[j] 构成逆序对i 后移。如果 L[i] R[j]那说明 L[i] 比 R[j] 大而且因为 L 是有序的L[i] 后面所有元素也都比 L[i] 大自然也都比 R[j] 大。于是从 i 到 L 的末尾这一整段全部和 R[j] 构成逆序对——一次就统计出一批逆序对数量是 L长度减去 i 的位置。你看明白这个逻辑的巧妙之处了吗在暴力解法里一个 R[j] 要和左边所有比它大的元素分别比较但在归并排序里因为 L 已经有序一旦发现 L[i] R[j]就能确定 L[i]、L[i1]……L[mid] 全都大于 R[j]然后一口气累加 mid - i 1 个数。单次比较引发的统计量从1变成了一堆这就是 O(n log n) 的来源。2.3 手算一遍数组 [7, 5, 6, 4] 的完整推演光说理论容易飘我拿一个经典小数组走一遍完整流程。假设 nums [7, 5, 6, 4]。第一层拆mid 1左半边 [7, 5]右半边 [6, 4]。左半边再拆[7] 和 [5]各自只有一个元素不用再拆。合并 [7] 和 [5]左指针在 7右指针在 5。7 5所以 7 这一整个左区间只有一个元素都和 5 构成逆序对累加 1。合并结果是 [5, 7]。右半边同理[6] 和 [4]6 4累加 1。合并结果是 [4, 6]。回到顶层合并 [5, 7] 和 [4, 6]左指针指向 5右指针指向 4。5 4左区间从 5 开始到末尾 [5, 7] 都大于 4累加 2。右指针移到 6。5 6左指针右移到 7。7 6左区间从 7 到末尾 [7] 都大于 6累加 1。右指针移到末尾左区间还剩 [7]全部拷贝。三次合并共累加 1 1 2 1 5。验证一下原数组 [7, 5, 6, 4] 的逆序对(7,5)、(7,6)、(7,4)、(5,4)、(6,4)确实是 5 对一个不多一个不少。注意顶层合并时一次累加 2 的效果——这就是批量结算的直观感受。2.4 为什么这个算法是 O(n log n) 而不是 O(n^2)归并排序每一层合并的总工作量是 O(n)因为每一层的所有区间加在一起恰好覆盖整个数组长度 n而数组被递归拆分成 log n 层每次折半。所以总复杂度 O(n log n)。相比暴力的 O(n^2)当 n 10^5 时暴力要比较大约 10^10 次归并排序只要大约 10^5 × 17 次差距接近六个数量级。这也是为什么所有高效逆序对解法都离不开分治或者树状数组这类低复杂度框架——不是技巧炫技是数据规模逼着你必须这么做。3. 代码落地C 和 Python 两版实现的关键差异3.1 C 版注意临时数组的作用域和引用传递C 写这个题最稳妥的姿势是直接在递归函数内部维护一个临时数组或者作为成员变量复用。我推荐在类里开一个全局的 temp 数组避免每次递归都 vector 拷贝导致额外的 O(n log n) 内存开销和拷贝耗时。核心代码直接给出来class Solution { private: vectorint temp; long long mergeCount(vectorint nums, int l, int r) { if (l r) return 0; int mid l (r - l) / 2; long long cnt 0; cnt mergeCount(nums, l, mid); cnt mergeCount(nums, mid 1, r); int i l, j mid 1, p 0; while (i mid j r) { if (nums[i] nums[j]) { temp[p] nums[i]; } else { cnt mid - i 1; // 关键批量累加 temp[p] nums[j]; } } while (i mid) temp[p] nums[i]; while (j r) temp[p] nums[j]; for (i l, p 0; i r; i, p) { nums[i] temp[p]; } return cnt; } public: long long reversePairs(vectorint record) { temp.resize(record.size()); return mergeCount(record, 0, record.size() - 1); } };注意我用了 long long 作为返回类型这个细节下面专门说。还有递归函数里cnt mergeCount(...)这两个递归调用必须写在合并前还是合并后没区别因为左右两侧内部的逆序对已经在它们的合并阶段统计完了我们只需要保证顶层合并前左右各自有序即可。顺序不影响正确性。3.2 Python 版优雅但注意递归深度Python 写分治通常比 C 松弛一些但有两个坑必须提前规避一是temp列表的传递方式二是递归深度。class Solution: def reversePairs(self, record: List[int]) - int: nums record n len(nums) temp [0] * n def merge_sort(l: int, r: int) - int: if l r: return 0 mid (l r) // 2 cnt merge_sort(l, mid) merge_sort(mid 1, r) i, j, p l, mid 1, l while i mid and j r: if nums[i] nums[j]: temp[p] nums[i] i 1 else: cnt mid - i 1 temp[p] nums[j] j 1 p 1 while i mid: temp[p] nums[i] i 1 p 1 while j r: temp[p] nums[j] j 1 p 1 for k in range(l, r 1): nums[k] temp[k] return cnt return merge_sort(0, n - 1)Python 里temp直接闭包引用外层的 list不需要重新赋值。递归深度要注意当 n 很大时Python 默认递归深度是 1000归并排序递归深度是 log n约 17~20所以纯递归没问题。但如果你把递归改成 while 模拟或者某些极端写法里递归深度变成 O(n)就会碰 RecursionError。归并排序天然深度 O(log n)所以这点其实很安全。3.3 为什么合并时必须做稳定排序式的 判断代码里用的是if nums[i] nums[j]注意这里的等号。有人会问改成严格小于nums[i] nums[j]行不行分情况讨论。如果是求逆序对题目定义是 nums[i] nums[j] 才算一对相等不算。那么合并时如果左指针的值等于右指针的值应该让左指针先走即 nums[i] nums[j] 时走左指针这样相等元素不会被误判为逆序对。这是稳定性的要求也决定了排序后相等元素相对顺序不变。如果你把判断条件改成严格小于一旦相等元素出现右指针可能先走导致它被错误地统计进逆序对里。我当初第一次写的时候就用错了条件结果测试数组 [1, 2, 1, 1] 一直多算两对排查了很久才意识到是等于号的问题。这个细节虽然一行但足以让整道题全错。4. 边界问题、取模陷阱与调试心得4.1 数据范围为什么逼你用 long long逆序对的最大数量是 C(n, 2) n × (n-1) / 2。如果 n 10^5最大逆序对数大约是 5 × 10^9远超 int 的 2^31 - 1约 2.1 × 10^9。所以只要你用 int 存结果在最坏情况数组严格降序下必然溢出提交就会得到莫名其妙的错误答案。我的建议是不管题目数据范围写没写一律用 long long。30 位以内够用吗如果 n 是 10^9 量级long long 也扛不住但那种规模通常不会用归并排序硬做。工程上long long 是逆序对题型的默认安全选择。C 里注意mid - i 1这个表达式的类型i 和 mid 是 int但它们参与累加时编译器会自动提升到 long long所以只要 cnt 是 long long 就没问题。Python 读者倒是不用担心溢出——Python 的 int 是任意精度。但 C 就得老老实实写对类型这是初学者最容易忽略又最致命的地方。4.2 取模要求的处理不是最后取一次就完事有些版本的题目要求返回结果对 1000000007 取模比如某些大厂笔试题变体。这时候有个坑不能只在 return 前取模。因为在递归中途cnt 可能已经越过 int 甚至 long long 的范围导致提前溢出最后取模也救不回来。正确做法有两种整个 cnt 都全程用 long long中途不做任何取模只在最终 return 前取模。这要求 n 不太大long long 能全程装下最大值。如果 n 特别大比如 10^6 以上在累加时每加一次就取一次模也就是cnt (cnt mid - i 1) % MOD。但千万注意第二种做法里返回值本身是取模后的而取模后的 cnt 再参与递归统计是安全的因为逆序对数量只做加法取模满足加法交换律和结合律。不过有个问题如果中途取模递归排序时的比较大小判断不受影响因为排序只关心元素值不关心计数。所以两种做法正确性都没问题区别是性能每步取模有一点点额外开销但可以接受。我个人的经验是能不取模就不取模肝语言特性题时但如果题面写了取模简化起见还是在累加的同时每一步用cnt (cnt ...) % MOD省得最后忘了。4.3 合并边界最容易翻车的地方递归出口是 l r不是 l r。因为某些写法 mid 计算可能让区间划分出问题虽然归并排序通常不会导致 l r但二手习惯任何递归都写成if (l r) return;更安全。循环条件while (i mid j r)里的等号必须写。漏掉等号会导致左右区间剩余元素没有被处理完虽然排序结果可能还是对的因为后面有两个 while 兜底但对逆序对统计来说漏掉的元素可能是逆序对——尤其在右指针 j 走完后左指针剩余元素不会额外产生新的逆序对因为在前面循环里该统计的已经统计完了。如果你漏了等号导致提前跳出前面循环少执行了一次该在循环里统计的逆序对可能刚好漏掉。还有 mid 的计算要用l (r - l) / 2不要用(l r) / 2。虽然对普通小数组这俩没区别但 l r 在极端边界r 接近 INT_MAX时可能溢出养成本能性写前者能避免很多潜在 bug。这种看起来等价但实际有坑的细节最容易在面试手撕代码时翻车。4.4 对数器验证别急着提交先暴力对拍写算法题我发现最有效的自检不是静态读代码而是写一个暴力解法和自己的高效解法做对拍。随机生成小数组长度 1 到 10元素数值范围 -100 到 100各跑 1000 次比较两种结果是否一致。对拍器代码很简单我通常直接在主函数里跑随机测试bool test() { Solution s; for (int t 0; t 1000; t) { int n rand() % 10 1; vectorint a(n); for (int i 0; i n; i) a[i] rand() % 201 - 100; vectorint b a; int ans1 s.reversePairs(a); int ans2 0; for (int i 0; i n; i) for (int j i 1; j n; j) if (b[i] b[j]) ans2; if (ans1 ! ans2) return false; } return true; }这个对拍器几乎能抓住 90% 以上的边界问题负数、相等元素、空数组、单元素数组全都能测到。我第一次写逆序对的时候就是靠它发现条件错误的。真的强烈建议每个人都养成这个习惯尤其是分治、递归这类容易小边界出错的题型。5. 从逆序对看分治思维相关变体与工程启发5.1 同源问题分治法求数组最大元素的位置热词里的分治法求一个n元素数组中最大元素的位置和逆序对是同一个专题的两道兄弟题。思路也是拆成左右两边分别求左边最大值的位置和右边最大值的位置再比较两个最大值谁更大谁就是全数组最大值。代码核心长这样int findMaxPos(vectorint nums, int l, int r) { if (l r) return l; int mid l (r - l) / 2; int leftPos findMaxPos(nums, l, mid); int rightPos findMaxPos(nums, mid 1, r); return nums[leftPos] nums[rightPos] ? leftPos : rightPos; }这个题很直白地展示了分治的最小化思想先递归到单元素再在每层合并时比较并选出胜者。和逆序对的区别在于最大元素位置在合并时只需要常数次比较而逆序对在合并时利用有序性做了批量统计。但两者的递归骨架完全同源你先学会其中一个另一个几乎就是顺手的事。5.2 树状数组解法另一种统计逆序对的思路分治不是唯一解法。逆序对还能用树状数组Fenwick Tree做原理是离散化 顺序扫描 前缀查询。大致思路把数组元素离散化成排名然后从左往右扫描每遇到一个元素就查询已经扫描过的元素里比它大的数量然后把它自己加进树状数组。这里查询和修改都是 O(log n)总复杂度同样是 O(n log n)。两种解法怎么选归并排序版不依赖离散化适合直接处理而且分治思想更容易在面试中现场讲清楚树状数组版代码更短大约 20 行但引入离散化和树状数组两个额外概念如果面试官让你现场证明正确性解释成本更高。我一般建议面试首选归并排序因为写法天然和分治专题契合工程或比赛里如果对线段树、树状数组更熟用树状数组成熟度更高。别贪多先把归并排序版本写到肌肉记忆级别。5.3 变体翻转对LeetCode 493另一个常见变体是 LeetCode 493 翻转对统计 i j 且 nums[i] 2 * nums[j] 的对数。归并排序同样适用但注意合并时不能直接在排序比较里统计——因为条件带了一个 2 倍关系你不能只在nums[i] nums[j]的分支里顺手统计。处理方式是在合并前对左区间依次查找右区间中有多少元素满足 nums[i] 2 * nums[j]也就是一个额外的双指针扫描然后再做正常的合并排序。这个变体进一步说明归并排序的框架是灵活的真正难点在于统计什么、在哪个阶段统计。5.4 工程上的启发合并阶段的增量信息从逆序对这个题里我最想分享的一点是分治不是单纯把问题拆开再拼回去而是要在合并阶段捕捉那些只有合并才能看清的增量信息。暴力的逆序对统计为什么会慢因为它每一次比较都是孤立的没有任何信息可以被复用。归并排序之所以快是因为排序让左右区间的内部结构变得有序于是某个右元素比多少个左元素小这个问题从一个一个数变成了左区间剩余长度这个 O(1) 的结论。本质上排序产生的有序性就是一种可以被复用的数据预处理信息。我在实际工作里其实不太会手写归并排序——大多数语言自带 sort。但分治思想本身到处都有git merge 的过程是分治合并SQL 的归并连接是分治外排分布式系统里 MapReduce 的 shuffle 阶段也是大排序拆成小排序再合并。搞懂逆序对这一道题你不仅刷了一道算法题还理解了一个非常底层的计算机思维模式先让局部有序再让局部之间的比较变得廉价。5.5 给初学者的刷题路径建议如果你刚接触分治我建议按这个顺序训练先写归并排序本身不要统计任何东西纯排序跑通。在纯归并排序的合并函数里加上cnt mid - i 1这一行跑逆序对题。跑完这道题换分治法求最大元素位置这类简单题体会拆解 比较的骨架。再挑战翻转对体会合并前额外统计的变化。每一步都要配对数器随机验证。很多初学者卡在这道题是卡在为什么排序能统计逆序对这个思维转换上。我的建议是别光看题解自己拿几张纸按第 2 节那样手推数组 [7, 5, 6, 4] 的完整递归树把每一层合并产生的累加数写在旁边。你亲手推一遍比看十遍题解都管用。逆序对这道题看起来小但它把分治、归并、稳定性、数据范围、边界条件这些要素全串在了一起。把它彻底吃透你后面在面试里遇到任何排序变体的题目都会比没刷过的人多一层底气。