分治法求逆序对数量的核心是在归并排序合并阶段统计跨左右子数组的逆序对，时间复杂度o(n log n)；逆序对定义为inums[j]，分治将其分为左、右和跨越三类，前两类递归处理，第三类在归并时通过比较leftarr[i]与rightarr[j]并累加(mid-i+1)高效统计。
用分治思想求逆序对数量，核心是借助归并排序的过程，在合并两个有序子数组时，统计跨左右两部分的逆序关系。时间复杂度稳定为 O(n log n)，远优于暴力 O(n²) 方法，是面试中考察分治与算法优化的经典题型。
逆序对的定义和分治切入点
逆序对指满足 i nums[j] 的数对 (i, j)。暴力枚举需双重循环，而分治的关键洞察是：所有逆序对只可能出现在三类位置——
- 完全在左半区间（递归处理）
- 完全在右半区间（递归处理）
- 左元素 > 右元素（即 i 在左、j 在右，这是合并阶段可高效统计的部分）
前两类交给递归，第三类在归并时顺手解决，避免重复检查。
归并过程中如何统计跨区逆序对
假设 leftArr 和 rightArr 已分别排好序。在归并时，用两个指针 i、j 遍历左右数组。当 leftArr[i] > rightArr[j]，说明 leftArr[i] 及其后面所有元素（因 leftArr 升序）都大于 rightArr[j] —— 这些都构成逆序对。
例如：
leftArr = [3, 5, 7], rightArr = [2, 4, 6]
比较 3 和 2：3 > 2 → 说明 leftArr 中从索引 i 开始的 (3 - i) = 3 个元素（3,5,7）都与 2 构成逆序对 → 累加 3
然后 j++，继续比较 3 和 4：3
后续类似，每次 rightArr[j] 被选中时，若 leftArr[i] > rightArr[j]，就加 (mid - i + 1)
实现要点与常见易错细节
写代码时注意几个关键点：
- 递归边界：l >= r 时返回 0（单个或空元素无逆序对）
- 下标计算：设当前区间为 [l, r]，中点 mid = l + (r - l) / 2；左区间 [l, mid]，右区间 [mid+1, r]
- 临时数组：归并时用辅助数组暂存排序结果，再拷回原数组，避免影响上层递归的索引逻辑
- 逆序对计数时机：只在“将 rightArr[j] 放入合并数组”且 leftArr[i] > rightArr[j] 时累加 (mid - i + 1)，不是每次比较都加
- 数据范围：逆序对总数可能超 int，建议用 long 类型存储结果
参考代码结构（Java）
主体逻辑简洁清晰：
public long reversePairs(int[] nums) {if (nums == null || nums.length return mergeSort(nums, 0, nums.length - 1);
}
private long mergeSort(int[] arr, int l, int r) {
if (l >= r) return 0;
int mid = l + (r - l) / 2;
long res = mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r);
res += merge(arr, l, mid, r);
return res;
}
private long merge(int[] arr, int l, int mid, int r) {
int[] temp = new int[r - l + 1];
int i = l, j = mid + 1, k = 0;
long count = 0;
while (i if (arr[i] temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
count += (mid - i + 1); // 关键：左边剩余元素全大于 arr[j]
}
}
// 复制剩余部分
while (i while (j // 写回原数组
System.arraycopy(temp, 0, arr, l, temp.length);
return count;
}
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
