LeetCode 493. 翻转对

2021-04-20 HGNULB 约 6 分钟

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

分类

LeetCode CodeTop 困难 已解决 未掌握 1-2 腾讯

标签

数组 二分查找 分治 有序集合 线段树 归并排序 树状数组

题目描述

✅ 493. 翻转对

题意分析

统计原数组中满足 i < j 且 nums[i] > 2 * nums[j] 的下标对数量。每一对按两个位置区分，元素可以重复，也可以为负数。

这里比较的是右侧值的两倍，不能当成普通逆序对，也不能仅根据两个值是否相等决定是否计数。直接枚举所有下标对需要平方时间，可以在归并排序过程中利用两个有序半区批量统计。

解法：归并排序计数

核心思路

[!blue]

把当前区间按下标分成左右两半，所有答案恰好分为三类：两个位置都在左半、都在右半、一个在左半而另一个在右半。递归分别统计前两类，并将各自区间排好序，本层再统计跨半区的配对，三类之间不会重复。

对跨区间配对，左半的所有元素原本都位于右半元素之前，所以 i < j 已由原来的区间归属保证。两半各自在内部排序不会改变这种归属，只需比较左值是否严格大于右值的两倍。

两半排序后，固定一个左值时，符合条件的右值一定构成右半的一个前缀：右值从小到大排列，乘以正数二仍然保持这个顺序。用 j 指向第一个不满足条件的位置，或右半末尾之后的位置，本次贡献就是 j - (mid + 1)。

按从小到大枚举左值时，之前符合条件的右值仍然符合，满足条件的前缀只可能变长，j 不需要回退。每个左元素都要加上整个有效前缀的长度，而不是只加本轮新增长度，因为同一个右元素可以分别与多个左侧位置组成不同下标对。

跨区间统计完成后，再用普通归并把两半按数值大小合为有序区间，交给上一层使用。如果提前将两半混合，就会失去原区间的左右归属；归并比较也仍用普通大小关系，不能改成翻转对的两倍条件。

比较时在乘法前转换为 64 位，避免右值乘二先在 32 位中溢出。负数同样满足上述单调关系，两个相等的负值甚至也可能构成翻转对，因此必须始终按原不等式判断。

解题步骤

1. 空区间或单节点区间返回零。
2. 递归处理左右半区，累加各自的计数，此时两半分别有序。
3. 令右指针从 mid + 1 开始，依次枚举左半元素，持续推进仍满足两倍条件的右指针。
4. 对每个左元素累加整个有效右前缀长度，右指针不重置。
5. 用共享临时数组完成普通有序归并，再复制回当前区间并返回计数。

代码实现

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++) {
            // 在乘法前使用 64 位整数，严格大于才计数。
            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);
    }
}

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++ {
        // 在乘法前使用 64 位整数，严格大于才计数。
        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 + 1))$，每层跨区间统计中两个指针只向前移动，随后归并也是线性操作，总共对数层。
• 空间复杂度：$O(n)$，临时数组供所有递归区间复用，递归栈另占 $O(\log n)$。本实现结束后原数组会被排序。

关键点总结

[!green]

• 固定顺序：递归、统计、归并。
• 指针不回退：右半有效前缀单调扩大，避免重复扫描。
• 计数与比较分开看：n 最多 50000 时，配对数最多 1,249,975,000，可用 int；两倍比较必须提升位宽。

易错点总结

[!yellow]

• 按普通逆序对计数：这里要求严格大于右值的两倍，不能只判断左值较大。
• 两倍乘法之后再转换类型：溢出已发生时无法恢复，应先用宽整数运算。
• 直接排除所有相等值：相等的负数仍可能满足两倍条件，应按数值不等式比较。
• 每次重新扫描右半：会失去单调指针带来的线性统计成本。
• 只加右指针本轮推进量：会漏掉当前左值与先前已经满足条件的右值之间的配对。
• 统计之前先归并混合两半：原左右区间的下标先后关系会被破坏，无法直接计跨区间对。

相似题目

题目	难度	关联与区别
315. 计算右侧小于当前元素的个数	困难	同样在归并时计跨区间数对，本题比较左值与右值两倍，不能直接按普通逆序关系累计。
327. 区间和的个数	困难	同样用排序后的两侧窗口批量统计满足数值范围的组合。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2021/52622596

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！