LeetCode 493. 翻转对

2021-04-20 HGNULB 约 14 分钟

文章信息 7 个分类 8 个标签

分类

题目描述

✅ 493. 翻转对

题意分析

要统计满足两个条件的下标对 (i, j) 的个数：位置上 i 必须在 j 前面，数值上前者必须大于后者的两倍。注意这是严格大于，且系数 2 打破了逆序对里「比较双方对称」的性质——nums[i] > 2 * nums[j] 与元素间的大小顺序并不等价，比如 3 和 2 满足普通逆序但不满足翻转对。

数组长度上限五万，双重循环约十二亿次比较，必然超时。这个规模配上「统计满足某种偏序关系的下标对数量」这种题型，指向的是 $O(n \log n)$ 量级的算法。

元素取值范围是完整的 int 区间，包含负数且能取到 $\pm 2^{31}$ 边界。这一条是本题的隐形陷阱：2 * nums[j] 在 int 下必然溢出，且负数乘 2 后变得更小，「乘二」这个操作对正负号的影响方向相反，不能想当然地把不等式两边约掉。

边界上要考虑：数组可能只有一个元素甚至为空，答案为 0；全部元素相等时答案为 0（因为要求严格大于两倍）；答案本身最大约为 $n^2/2 \approx 1.25 \times 10^9$，超过了 int 上限，中间累加必须留足位宽。

解法：归并排序计数

核心思路

暴力做法是枚举所有 i < j 的下标对逐一检验，$O(n^2)$，在五万长度下直接超时。瓶颈很清楚：每一对都被独立检查了一次，完全没有利用「一批元素之间的相对大小关系可以被批量比较」这件事。

关键观察分两层。第一层是分治的可加性：把数组从中间切成左右两半，那么任何一个满足条件的下标对，要么两个下标都落在左半、要么都落在右半、要么 i 在左而 j 在右，三种情形互斥且穷尽。于是总数 = 左半内部的数量 + 右半内部的数量 + 跨越中线的数量，前两项递归求解，问题就归结为「如何快速数出跨越中线的对数」。

第二层是排序不改变跨区间的答案：跨区间的对 (i, j) 中，i 恒在左半、j 恒在右半，位置约束 i < j 已经被「左半整体在右半之前」自动满足了。因此左半内部怎么重排、右半内部怎么重排，都不影响跨区间的对数。既然顺序无所谓，就可以先把两半各自排成升序，再利用有序性做批量统计——这正是把统计过程嵌进归并排序的理由。

有了两半有序这个条件，跨区间统计可以用一对单调指针完成。固定左半的元素 nums[i]（i 从左往右递增，值也随之递增），去右半找出所有满足 nums[i] > 2 * nums[j] 的 j。由于右半升序，满足条件的 j 必然是右半的一个前缀：nums[j] 越小越容易满足。设这个前缀的右端点为 j，则贡献的对数就是 j - (mid + 1)。

这里的单调性是效率的来源：当 i 右移时 nums[i] 不减，条件 nums[i] > 2 * nums[j] 只会更容易满足，因此前缀端点 j 只会右移、绝不回退。于是 j 在整个合并阶段只需从 mid+1 单向走到 right，两层循环的实际总代价是线性而非平方。

由此写出算法的不变量：函数 mergeSort(nums, left, right) 返回该区间内部翻转对的数量，并在返回时保证 nums[left..right] 已升序。这两件事必须同时成立——前者是答案，后者是上层调用能继续用单调指针的前提。执行顺序也随之固定：先递归（此时两半各自变得有序），再统计跨区间对数（依赖有序性），最后归并（把两半合成一段有序）。统计必须夹在递归与归并之间，早一步右半无序，晚一步左右两半已经混在一起无法区分。

数值边界校正：32 位有符号整数的精确范围是 $[-2^{31}, 2^{31}-1]$，正上界不是 $+2^{31}$。当 $n \le 50000$ 时，翻转对总数最多为 $n(n-1)/2 = 1,249,975,000$，小于 Integer.MAX_VALUE = 2,147,483,647，所以返回值和计数器使用 int 足够；必须提升到 64 位的是比较中的 2 * nums[j]，因为该乘积可能越过 32 位范围。

解题步骤

递归出口写 left >= right 时返回 0。长度为 1 或 0 的区间内部不可能有下标对，且天然有序，两条不变量都自动成立。

取中点后先递归左右两半并累加返回值。之所以必须先递归，是因为统计跨区间对数依赖「两半已升序」，而这个性质正是由递归的第二条不变量提供的。

在归并之前，用双指针统计跨区间对数。i 遍历左半的每个位置，j 从 mid + 1 出发且声明在外层循环之外——这是全题最关键的一行，j 不重置才能保证单调推进，若放在循环内部初始化，复杂度会退回 $O(n^2)$。

内层 while 的条件写成 j <= right && (long) nums[i] > 2L * nums[j]。转成 64 位是因为 nums[j] 可以取到 int 边界，2 * nums[j] 在 int 下会溢出翻转符号，把不满足的对误判成满足。j <= right 的越界保护要写在前面，靠短路求值避免读到区间外的数据。

累加 j - (mid + 1)。这个差值就是右半中已被 j 越过的元素个数，也就是当前 i 能配出的对数。因为 j 不回退，它天然是「累计前缀长度」而非「本轮新增」，所以每个 i 都要重新累加一次完整前缀，而不是只加增量。

最后执行标准归并，把两半合成升序写回原数组。归并用一个临时缓冲区先装结果再拷回，避免在原地写入时覆盖尚未读取的元素。

乘法比较必须提升到 64 位，计数在题目约束下可用 int。当 $n \le 50000$ 时，任意下标对总数最多为 $n(n-1)/2=1,249,975,000$，没有超过 32 位有符号整数；真正必然有溢出风险的是 2 * nums[j]。

以 nums = [2, 4, 3, 5, 1] 走一遍。递归到最底层后逐层回溯。

先看左半 [2, 4, 3]（下标 0..2，mid = 1）。它自己又分成 [2, 4]（下标 0..1）和 [3]（下标 2）。处理 [2, 4]：再分成 [2] 和 [4]，各返回 0；统计阶段 i = 0 时 nums[0] = 2，检查 2 > 2 * 4 = 8 不成立，j 停在 1，贡献 1 - 1 = 0；归并后仍为 [2, 4]。回到 [2, 4, 3] 这层：左半是已排好的 [2, 4]，右半是 [3]。i = 0 时 2 > 2 * 3 = 6 不成立，j 停在 2，贡献 0；i = 1 时 4 > 6 不成立，j 仍为 2，贡献 0。归并后数组前三位变成 [2, 3, 4]，左半共返回 0。

再看右半 [5, 1]（下标 3..4，mid = 3）。分成 [5] 和 [1] 各返回 0。统计阶段 i = 3 时 nums[3] = 5，检查 5 > 2 * 1 = 2 成立，j 从 4 推进到 5；此时 j <= right 不成立，循环停止，贡献 5 - 4 = 1。归并后后两位变成 [1, 5]，右半返回 1。

最后是顶层（left = 0, right = 4, mid = 2），此时数组为 [2, 3, 4, 1, 5]，左半 [2, 3, 4] 与右半 [1, 5] 各自有序。统计阶段 j 初始为 3：i = 0，2 > 2 * 1 = 2 不成立（严格大于，等于不算），j 停在 3，贡献 0；i = 1，3 > 2 成立，j 推进到 4，再检查 3 > 2 * 5 = 10 不成立，j 停在 4，贡献 4 - 3 = 1；i = 2，4 > 10 不成立，j 仍为 4，贡献 4 - 3 = 1。跨区间共 2 对。

总计 0 + 1 + 2 = 3。手工核对原数组 [2, 4, 3, 5, 1]：满足条件的下标对是 (1, 4) 即 4 > 2×1、(2, 4) 即 3 > 2×1、(3, 4) 即 5 > 2×1，恰好三对，答案一致。注意 i = 1 那一轮体现了 j 不回退的价值——它承接了上一轮留下的位置继续推进，而 i = 2 那一轮直接复用了 j 的当前值，一次比较都没多做。

代码实现

// 归并时先统计右侧满足 nums[i] > 2 * nums[j] 的数量。
class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, new int[nums.length], 0, nums.length - 1);
    }

    private int mergeSort(int[] nums, int[] temp, int left, int right) {
        if (left >= right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, temp, left, mid)
                + mergeSort(nums, temp, mid + 1, right);

        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            while (j <= right && (long) nums[i] > 2L * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
        }

        merge(nums, temp, left, mid, right);
        return count;
    }

    private void merge(int[] nums, int[] temp, int left, int mid, int 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 {
                temp[k++] = nums[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = nums[i++];
        }

        while (j <= right) {
            temp[k++] = nums[j++];
        }

        System.arraycopy(temp, left, nums, left, right - left + 1);
    }
}

// 归并时先统计右侧满足 nums[i] > 2 * nums[j] 的数量。
func reversePairs(nums []int) int {
	temp := make([]int, len(nums))
	return mergeSort(nums, temp, 0, len(nums)-1)
}

func mergeSort(nums []int, temp []int, left int, right int) int {
	if left >= right {
		return 0
	}

	mid := left + (right-left)/2
	count := mergeSort(nums, temp, left, mid) + mergeSort(nums, temp, mid+1, right)

	j := mid + 1
	for i := left; i <= mid; i++ {
		for j <= right && int64(nums[i]) > 2*int64(nums[j]) {
			j++
		}
		count += j - (mid + 1)
	}

	merge(nums, temp, left, mid, right)
	return count
}

func merge(nums []int, temp []int, left int, mid int, right int) {
	i, j, k := left, mid+1, left

	for i <= mid && j <= right {
		if nums[i] <= nums[j] {
			temp[k] = nums[i]
			i++
		} else {
			temp[k] = nums[j]
			j++
		}
		k++
	}

	for i <= mid {
		temp[k] = nums[i]
		i++
		k++
	}

	for j <= right {
		temp[k] = nums[j]
		j++
		k++
	}

	copy(nums[left:right+1], temp[left:right+1])
}

复杂度分析

时间复杂度：$O(n \log n)$。递归树有 $O(\log n)$ 层；每层中，所有区间的跨区间统计与归并总共各扫描 $O(n)$ 个元素。右指针不为每个左元素重置，因此统计也是线性的；若重置，递推式会变成 $T(n)=2T(n/2)+O(n^2)$，整体退化为 $O(n^2)$。

空间复杂度：$O(n)$。Java/Go 实现都只申请一次长度为 n 的临时数组并在递归间复用；递归栈为 $O(\log n)$，不改变量级。

关键点总结

「统计满足偏序关系的下标对」优先想分治：这类问题的公共骨架是「左内 + 右内 + 跨越」三段相加，而跨越部分往往能借助两侧有序做到线性。识别信号是「下标有先后要求 + 数值有大小要求 + 只要个数不要具体是哪些对」，逆序对、小和、区间和个数都套用同一模板。

想清楚为什么可以打乱顺序：跨区间统计之所以允许两半各自排序，是因为位置约束已经由「左半整体在右半之前」承担了，数值比较与半区内部顺序无关。这一步是整个算法合法性的核心，面试中必须主动讲出来，否则会被质疑「排序不是把下标关系破坏了吗」。

单调指针不回退是复杂度的唯一来源：把 j 声明在外层循环之外，靠 nums[i] 递增推出 j 单调递增。凡是双层循环里内层指针能不回退的场景，都要警觉是否可以省掉一层。写完代码后，专门检查一遍「哪些变量被错误地放进了内层作用域」是个很有价值的习惯。

执行顺序不可交换：递归 → 统计 → 归并，三步的先后由不变量决定。统计放到归并之后，左右两半已经混在一起，再也分不出哪些下标属于左半；统计放到递归之前，两半无序，单调指针失效。能说清「为什么必须夹在中间」，说明真正理解了算法而非背模板。

系数与严格性都要盯死：条件是 nums[i] > 2 * nums[j] 而非 nums[i] > nums[j]，也不是大于等于。系数 2 让比较不再与归并时用的比较一致，所以统计不能顺手写进归并循环里省事——那是逆序对的写法，本题必须独立扫一遍。

面试视角：标准表达顺序是「下标对三分 → 递归保证两半有序 → 单调指针统计跨区间对 → 归并恢复不变量」。若追问其它路线，可以说明离散化加树状数组也能做到 $O(n \log n)$，但需要处理 nums[i] 与 2 * nums[i] 的坐标和查询边界。

易错点总结

错误写法：比较时不做 64 位提升，直接写 nums[i] > 2 * nums[j]。用例 nums = [2147483647, -2147483648] → 2 * (-2147483648) 在 int 下溢出成 0，判定 2147483647 > 0 成立，答案返回 1；但正确判定应是 $2147483647 > -4294967296$，恰好也成立，结果侥幸对。换成 nums = [1, 1073741824] → 2 * 1073741824 溢出成 $-2147483648$，判定 1 > -2147483648 成立，凭空多算一对，返回 1 而正确答案是 0。

错误写法：把 int j = mid + 1 写进 for 循环内部。用例长度五万且跨区间存在大量翻转对时，每个 i 都从右半起点重新扫描，递推式变成 $T(n)=2T(n/2)+O(n^2)$，总复杂度退化为 $O(n^2)$；结果仍然正确，所以这个性能问题在小数据上不容易暴露。

错误写法：把统计逻辑直接套进 merge 的大小比较。用例 nums = [3, 2] 中，归并会因为 3 > 2 先取右侧元素，但翻转对条件 3 > 2 * 2 不成立，正确答案是 0。普通逆序对的判据与本题不同，必须单独统计。

错误写法：统计写在 merge 之后。用例 nums = [2, 4, 3, 5, 1] → 顶层归并完成后数组已是 [1, 2, 3, 4, 5]，左右两半的原始归属丢失，此时无论怎么扫都只能得到 0，最终答案严重偏小。

错误写法：累加时写成 count++ 或 count += 1。用例 nums = [5, 5, 5, 1, 1, 1] 的顶层两半已经分别有序，每个 5 都能与右侧三个 1 配对，跨区间贡献是 9；若每个 i 只加 1，只会得到 3。贡献是满足条件的右侧前缀长度，不是布尔值。

错误写法：贡献写成 j - mid 而不是 j - (mid + 1)。用例 nums = [1, 2] → 左半 [1]、右半 [2]，1 > 4 不成立，j 停在 mid+1 = 1，正确贡献是 0，写成 j - mid 得到 1，返回 1 而正确答案是 0。右半的起点是 mid+1，前缀长度必须以它为基准。

错误写法：看到相等元素就认为一定不构成翻转对。用例 nums = [-1, -1] 中，虽然两数相等，但 -1 > 2 * (-1) 成立，答案是 1。严格大于排除的是两边表达式相等，不是排除 nums[i] == nums[j]。

错误写法：内层 while 的两个条件写反顺序，即 (long) nums[i] > 2L * nums[j] && j <= right。用例 nums = [5, 1] → j 推进到 2 时先求值 nums[2]，越界抛异常（Go 里直接 panic）。越界保护必须写在最左边，依赖短路求值。

错误写法：复用临时数组时总从下标 0 拷回。递归处理右半区间时 left > 0，若写成 System.arraycopy(temp, 0, nums, left, len)，会把别的区间内容覆盖过来，破坏「返回时区间有序」的不变量。源和目标都必须从当前 left 开始。

错误写法：递归出口写成 left == right 返回 0。用例空数组 nums = [] → 主函数传入 right = -1，出口条件不成立，继续递归时 mid 计算出负值并访问 nums[-1] 越界崩溃。写 left >= right 才能同时兜住空区间。

错误写法：merge 结束后忘记把缓冲区拷回原数组。用例 nums = [2, 4, 3, 5, 1] → 上层拿到的两半仍是原始乱序，跨区间统计的单调指针前提被破坏，j 提前停住或过度推进，最终答案随机偏小；而小规模用例往往恰好蒙对，极难调试。

相似题目

题目	难度	考察点
剑指 Offer 51. 数组中的逆序对	困难	没有系数 2，判据与归并的比较完全一致，可以把计数直接融进归并循环省一趟扫描
315. 计算右侧小于当前元素的个数	困难	要求每个下标各自的答案而非总数，归并时必须携带原始下标才能把计数写回对应位置
327. 区间和的个数	困难	统计对象换成前缀和数组，且条件是落入区间而非单侧不等式，需要两个单调指针夹逼
912. 排序数组	中等	归并排序本身的裸题，可用来单独校验 merge 部分的边界与稳定性是否写对
53. 最大子数组和	中等	同为「左内 + 右内 + 跨越」的分治框架，但跨越部分靠向两侧扩展而非双指针计数