VIRTUALS

the virtual labs for the virtuals

0%

LeetCode 493. 翻转对

Posted on Edited on In ,

摘要：
归并排序模板题。

题目

给定一个数组 $nums$ ，如果 $i < j$ 且 $nums[i] > 2 \times nums[j]$ 我们就将 $(i, j)$ 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

  1. 给定数组的长度不会超过 $50000$。
  2. 输入数组中的所有数字都在 $32$ 位整数的表示范围内。

归并思想

这道题和AcWing归并排序模板题 【AcWing算法基础】第一讲-基础算法-归并排序 AcWing 788. 逆序对的数量 非常类似，都是利用区间的单调性对pair的比较进行优化。
递归地划分整个数组区间。从最小两个数（或一个数）开始「归」或者叫回溯，在回溯过程中对数组当前的两个区间进行排序，维护它们的单调性，为上一层做准备。同时，在这个过程中另行维护两个指针 i, j , 分别处理两个片段。判断条件nums[i] > 2*nums[j]。如果当前nums[i] > 2*nums[j]，由于此时 i 所在区间是单调递增的，所以从 i 到区间结束的地方所有的数都满足这个条件；反之，移动 i。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    long long res = 0;                                                              // 1
    int reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size() + 10);
        helper(nums, tmp, 0, nums.size() - 1);
        return res;
    }

    void helper(vector<int> &nums, vector<int> &tmp, int l, int r) {
        if (l >= r) return;
        int mid = l + r >> 1;
        helper(nums, tmp, l, mid), helper(nums, tmp, mid + 1, r);                   // 2
        // backtrack
        int i = l, j = mid + 1;                                                     // 3
        for (; i <= mid && j <= r;) {
            if (nums[i] > (long long) 2 * nums[j]) {                                // 4
                res += mid - i + 1;                                                 // 5
                j ++;                                                                   
            }
            else {
                i ++;                                                               // 6
            }
        }
        // sort                                                                     // 7
        i = l, j = mid + 1;                                             
        int t = 0;
        for (; i <= mid && j <= r;) {
            if (nums[i] > nums[j]) tmp[t ++] = nums[j ++];
            else tmp[t ++] = nums[i ++];
        }
        for (; i <= mid;) tmp[t ++] = nums[i ++];
        for (; j <= r;) tmp[t ++] = nums[j ++];
        for (int i = l, t = 0; i <= r;) nums[i ++] = tmp[t ++];
    }
};
  1. 因为题目给出数组长度不超过 $50000$，所以有 $49999!$ 个对数，显然结果最大超过 int 类型范围。
  2. 像二叉树遍历一样递归地将原数组一分为二。
  3. 维护两个指针分别处理两个片段。
  4. 因为 2 * nums[j] 可能会超出 int 类型最大可取值，所以需要强制转换成long long。
  5. 如果满足条件，那么由于片段内数组数字是单调递增的，所以从 i 起到片段结束都满足条件。接着移动 j，因为 j++ 后对应的数组数字增加，所以需要从 i 起和 j 重新比较。
  6. 不满足条件的话，移动 i ，看增加之后是否满足条件。
  7. 将两个片段作为一个整体排序，这个整体将作为回溯到上一层的一个片段。

注意这道题和 【AcWing算法基础】第一讲-基础算法-归并排序 AcWing 788. 逆序对的数量 的不同之处在于，后者可以在归并排序的两两比较的同时进行逆序对的计数，绝对不会漏掉。
但是这道题因为比较条件不同，如果在归并排序的同时进行计数，会漏掉一些数据。
比如数组排序到最后一层：

$1, 2, 3, 1, 3$

left: $1, 2, 3$, right: $1, 3$

会漏掉 $(3, 1)$ 这一对。

树状数组

等我学会之后再来完成。

原题链接： LeetCode 493. 翻转对