LCR 170：交易逆序对的总数（归并排序） —— 题解

👋 欢迎阅读

🔥愿旖旎· 个人主页

📘学习专栏：《算法专栏》《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 对：7>5、7>6、7>4、5>4、6>4），总比较次数只有 O(n log n) 级别。

2. 算法策略（归并排序 + 合并时计数）

核心步骤：

1. 递归拆分：取中点mid = left + (right - left) / 2，分别处理[left, mid]与[mid+1, right]。
2. 递归终止：if (left >= right) return;（单元素无逆序对）。
3. 升序合并：cur1指左段、cur2指右段，每次取较小者写入tmp。
4. 计数时机：当record[cur1] > record[cur2]（取右段元素）时，左段剩余[cur1, mid]全部大于它，累加ret += mid - cur1 + 1。
5. 收尾搬运：某段耗尽后，把另一段剩余元素搬入tmp（不计数）。
6. 回填：record[i] = tmp[i - left]，返回本层合并结果。

📊 示例（record = [7,5,6,4]，逆序对总数 = 5）：

三次计数分别在[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的位置，于是5>4、7>4恰好两对，个数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]回填时偏移必须减 left；ret用int即可（n = 5×10⁴时逆序对最多约1.25×10⁹，未超2^31）。
• 复杂度：时间 O(n log n)（log n 层合并，每层总扫描 O(n)），空间 O(n)（tmp）+O(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 { vector<int> tmp; // 辅助数组：所有合并轮次复用（只分配一次） int ret = 0; // 逆序对总数：跨递归层累计 public: int reversePairs(vector<int>& record) { int n = record.size(); tmp.resize(n); // 一次性开好，避免每次递归都分配 mergeSort(record, 0, n - 1); // 对闭区间 [0, n-1] 归并并计数 return ret; } void mergeSort(vector<int>& 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]不符）；两个分支都加则同一对会被计算两次，结果翻倍。
• <会让相等元素走累加分支，把"相等"误算成逆序对；逆序对要求严格大于，所以必须用<=取左段、相等不计数。

祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨