归并排序巧解逆序对问题：LeetCode 剑指 Offer 51.数组中的逆序对
1. 题目链接
剑指 Offer 51. 数组中的逆序对
题目要求：给定一个整数数组 record，返回数组中逆序对的总数。逆序对定义为 i < j 且 record[i] > record[j]。
2. 题目描述
- 输入：整数数组
record，例如[7,5,6,4]。 - 输出：逆序对总数，例如
5（对应逆序对：(7,5), (7,6), (7,4), (5,4), (6,4)）。 - 约束条件：
0 ≤ 数组长度 ≤ 50000- 结果可能很大，需对
1e9+7取模（本题代码未处理，需根据题目要求补充）。
3. 示例分析
示例：
输入：record = [7,5,6,4]
输出：5
分步解析：
-
分解数组：
- 初始数组分为
[7,5]和[6,4]。 - 左子数组
[7,5]的逆序对为1（7 > 5）。 - 右子数组
[6,4]的逆序对为1（6 > 4）。
- 初始数组分为
-
合并过程统计：
- 合并左数组
[5,7]和右数组[4,6]：- 比较
5和4：5 > 4→ 逆序对增加2（左数组剩余元素5,7均大于4）。 - 比较
5和6：5 ≤ 6→ 无新增。 - 比较
7和6：7 > 6→ 逆序对增加1（左数组剩余元素7大于6）。
- 比较
- 合并阶段总逆序对：
2 + 1 = 3。
- 合并左数组
-
总计：
1（左） + 1（右） + 3（合并） = 5。
4. 算法思路
归并排序与逆序对统计的结合
-
分治策略：
- 分解数组为左右子数组，递归计算各自的逆序对数量。
- 合并时统计跨越左右子数组的逆序对数量。
-
合并阶段的关键操作：
- 当左子数组元素
nums[cur1] > nums[cur2]时，左子数组剩余元素（从cur1到mid）均大于nums[cur2]，逆序对增加mid - cur1 + 1。
- 当左子数组元素
步骤拆解
- 递归分解：将数组二分至单个元素。
- 逆序对累加：
- 左子数组内部逆序对数目。
- 右子数组内部逆序对数目。
- 合并时左右之间的逆序对数目。
- 合并排序：确保合并后的子数组有序，为后续合并提供正确状态。
5. 边界条件与注意事项
-
递归终止条件： 当
left >= right时，子数组长度为0或1，无逆序对。 -
索引越界问题：中间点计算
mid = (left + right) / 2可能导致溢出，建议改为left + (right - left) / 2。 -
临时数组管理： 预分配临时数组
tmp的空间，避免递归中频繁分配内存。 -
稳定性处理：合并时若
nums[cur1] == nums[cur2]，优先插入左元素，但逆序对不增加。 -
复杂度分析：
- 时间复杂度：
O(n log n)，归并排序的时间复杂度。 - 空间复杂度：
O(n)，临时数组和递归栈空间。
- 时间复杂度：
6. 代码实现与解析
class Solution {
public:vector<int> tmp; // 全局临时数组，用于合并阶段int reversePairs(vector<int>& record) {tmp.resize(record.size()); // 预分配空间return mergeSort(record, 0, record.size() - 1);}int mergeSort(vector<int>& nums, int left, int right) {if (left >= right) return 0; // 终止条件：子数组长度为0或1int mid = (left + right) / 2; // 计算中间点int ret = 0;ret += mergeSort(nums, left, mid); // 左子数组逆序对数目ret += mergeSort(nums, mid + 1, right); // 右子数组逆序对数目// 合并并统计跨左右子数组的逆序对int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right) {if (nums[cur1] <= nums[cur2]) {tmp[i++] = nums[cur1++]; // 左元素小，无逆序对} else {ret += mid - cur1 + 1; // 统计逆序对tmp[i++] = nums[cur2++];}}// 处理剩余元素（不产生新逆序对）while (cur1 <= mid) tmp[i++] = nums[cur1++];while (cur2 <= right) tmp[i++] = nums[cur2++];// 将排序后的数据复制回原数组for (int j = left; j <= right; j++) {nums[j] = tmp[j - left];}return ret;}
};
代码逐行解析
-
全局临时数组
tmp：- 预分配空间，避免递归中频繁申请内存。
-
递归分解与统计：
mergeSort返回当前区间的逆序对总数，累加左右子数组的结果。
-
合并阶段的核心逻辑：
- 逆序对统计：当
nums[cur1] > nums[cur2]时，左子数组中剩余元素均构成逆序对，数量为mid - cur1 + 1。 - 稳定性处理：使用
<=保证相等元素不触发逆序对统计。
- 逆序对统计：当
-
剩余元素处理：
- 剩余元素直接追加到临时数组，不产生新逆序对。
-
数据回写：
- 将临时数组的数据复制回原数组的
[left, right]区间，确保后续合并正确。
- 将临时数组的数据复制回原数组的
总结
归并排序在合并阶段天然适合统计逆序对：左、右子数组有序时，可以高效计算跨越两部分的逆序对数量。通过分治策略，算法的时间复杂度为 O(n log n)，优于暴力法的 O(n²)。代码中需注意中间点计算的潜在溢出问题，以及临时数组的预分配优化。掌握这一方法，可解决多数分治类统计问题（如翻转对、右侧更小元素等）。