‘反向对’问题解决思路的一般原则

此文是对 LeetCode-493. 翻转对 国际站上高票回答中，一遍总结回答的翻译
原地址在此

‘反向对’问题解决思路的一般原则

看起来有一系列的解题思路（ (BST-based, BIT-based, Merge-sort-based)）。在这里，我想集中讨论这些解决方案背后的一般原则，以及这些解决方案可能应用于一些类似的问题。

基本思想很简单：分解数组并解决子问题。

数组的分解自然使我们想起子数组。为了统一下面的讨论，让我们假设输入数组是 nums，包含共 n 个元素。让 nums[i,j] 表示从索引 i 到索引 j（均包含）的子数组, T（i,j） 需要解决相同问题下的子数组（例如，对于反向对，T（i,j）将表示子数组 num[i,j] 的重要反向对的总数。

在上面的定义中，将我们原来的问题确定为 T（0，n - 1）。非常简单。现在的关键是如何从其子问题构建解决原始问题的解决方案。这实质上相当于为T（i，j）建立重复关系。因为如果我们能从它的子问题中找到T（i，j）的解决方案，我们肯定可以构建到更大的子数组的解决方案，直到包含最终整个数组。

虽然可能有许多方法可以建立T（i，j）的复发关系，但在这里，我将只介绍以下两个常见方法：

  1. T（i， j） = T（i， j - 1） + C，即元素将按顺序处理，C 表示处理子数组 nums[i， j] 的最后一个元素的子问题。我们将调用此顺序重复关系。

  2. T（i，j） = T（i，m） + T（m = 1，j） + C，其中 m = （i+j）/2，即子数组数 nums[i， j] 将进一步划分为两个部分，C 表示合并两个部分的子问题。我们将它称作此分区定期关系（直译，更像是子问题合并）。

无论哪种情况，子问题 C 的性质将取决于所考虑的问题，并且将决定原始问题的总体时间复杂性。因此，通常找到解决这个子问题的高效算法，以获得更好的时间性能是至关重要的。还要注意重叠子问题的可能性，在这种情况下，最好采用动态编程 （DP） 方法。

接下来，我将对这两个重复关系应用到此问题”反向对”，并列出一些解决方案供您参考。

I – Sequential recurrence relation（顺序重复关系）

我们还是假设输入数组是带 n 个元素的 nums，T（i，j） 表示数组 num[i， j] 的重要反向对的总数。对于顺序重复关系，我们可以设置 i = 0，即子数组始终从开头开始。因此，我们最终可以得到的：

T(0, j) = T(0, j - 1) + C

子问题 C 现在变为”对第一个元素来自子数组 nums[0，j - 1],第二个元素是 nums[j],查找重要反向对的数量”。

请注意，要将对（p、q）作为重要的反向对，必须满足以下两个条件

  1. p < q, 第一个元素下标在第二个元素之前
  2. nums[p] = 2 = nums[q]：第一个元素必须大于第二个元素的两倍。

对于子问题 C，自动满足第一个条件;因此，我们只需要考虑第二个条件，这相当于搜索子数组 num[0,j - 1] 中大于两倍的 num[j] 的所有元素。

直接的搜索方法是对子数组进行线性扫描，该子数组按 O（j） 的顺序运行。从顺序重复关系，这导致完整的的O（n^2）时间复杂度解法。

为了提高搜索效率，一个关键的观察是，子数组中元素的顺序并不重要，因为我们只对重要反向对的总数感兴趣。这表明我们可以对这些元素进行排序，并进行二进制搜索，而不是普通的线性扫描。

如果搜索空间（由将执行搜索的元素组成）是”静态的”（从运行前到运行后没有变化），将元素放入数组将非常适合我们执行二进制搜索。然而，情况并非如此。处理 j-th 元素后，我们需要将其添加到搜索空间，以便它可供搜索到以后的元素，从而随着处理越来越多的元素而扩展搜索空间。

因此，我们希望在搜索和插入操作之间取得平衡。数据结构（如二进制搜索树 （BST） 或二进制索引树 （BIT））为这两个操作提供了相对快速的性能，所以这是这类数据结构占上风的地方。

BST - based solution

我们会定义例子所示的树节点，val 是节点的值，cnt 是在当前节点的子树中所有比大于或等于 val 的个数

1
2
3
4
5
6
7
8
class Node {
    int val, cnt;
    Node left, right;
    Node(int val) {
        this.val = val;
        this.cnt = 1;
    }
}

下面是搜索和插入操作

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
private int search(Node root, long val) {
    if (root == null) {
        return 0;
    } else if (val == root.val) {
        return root.cnt;
    } else if (val < root.val) {
        return root.cnt + search(root.left, val);
    } else {
        return search(root.right, val);
    }
}

private Node insert(Node root, int val) {
    if (root == null) {
        root = new Node(val);
    } else if (val == root.val) {
        root.cnt++;
    } else if (val < root.val) {
        root.left = insert(root.left, val);
    } else {
        root.cnt++;
        root.right = insert(root.right, val);
    }
    return root;
}

最后是主方法，将元素本身插入BST的同时，将搜索所有元素，对不小于当前元素的两倍加1（转换为long类型以避免溢出）

注意：此自制的BST并非自平衡的，时间复杂度可能高达O（n ^ 2）（实际上，如果在此处复制并粘贴解决方案，则将获得TLE）。为了保证O（nlogn）性能，请使用自平衡BST之一（例如红黑树，AVL树等）。

1
2
3
4
5
6
7
8
9
public int reversePairs(int[] nums) {
    int res = 0;
    Node root = null;
    for (int ele : nums) {
        res += search(root, 2L * ele + 1);
        root = insert(root, ele);
    }
    return res;
}

BIT - based solution

对于 BIT，搜索和插入操作会是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private int search(int[] bit, int i) {
    int sum = 0;
    while (i < bit.length) {
        sum += bit[i];
        i += i & -i;
    }

    return sum;
}

private void insert(int[] bit, int i) {
    while (i > 0) {
        bit[i] += 1;
        i -= i & -i;
    }
}

在主程序中，我们将再次搜索大于当前元素两倍的所有元素，同时将元素本身插入BIT。对于每个元素，“索引”函数将在BIT中返回其索引。与基于BST的解决方案不同，它保证可以在O（nlogn）上运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int reversePairs(int[] nums) {
    int res = 0;
    int[] copy = Arrays.copyOf(nums, nums.length);
    int[] bit = new int[copy.length + 1];
    Arrays.sort(copy);
    for (int ele : nums) {
        res += search(bit, index(copy, 2L * ele + 1));
        insert(bit, index(copy, ele));
    }
    return res;
}

private int index(int[] arr, long val) {
    int l = 0, r = arr.length - 1, m = 0;
    while (l <= r) {
        m = l + ((r - l) >> 1);
        if (arr[m] >= val) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return l + 1;
}

有关基于BIT的解决方案的更多说明：

  • 我们希望对元素进行排序，因此输入数组的排序版本为copy。

  • 该 bit 基于此排序数组。它的长度比复制阵列的长度大一倍，以解决根问题。

  • 最初，bit 为空，然后开始对输入数组进行顺序遍历。对于每个元素，我们首先搜索整个 bit 以找到大于该元素两倍的所有元素，然后将结果添加到res中。然后我们将元素本身插入到位中以供将来搜索。

  • 请注意，按惯例，对 bit 搜索涉及从位的某个索引向根进行遍历，这将产生复制数组的预定义运行总计，直到对应的索引为止。对于插入，行进方向将相反，并从某个索引向位数组的末端移动。

  • 对于输入数组的每个扫描元素，其搜索索引将由 copy 中第一个元素的索引大于其两倍的索引给出（上移1以说明根），而其插入索引将是副本数组中第一个元素的索引，该索引不少于其自身（再次上移1）。这就是索引函数的作用。

  • 对于我们的情况，运行总计只是遍历过程中遇到的元素数。如果我们遵循上述约定，则运行总数将是小于给定索引处的元素数，因为复制数组是按升序排序的。但是，实际上，我们希望找到大于某个值（即所扫描元素的两倍）的元素数量，因此我们需要翻转约定。这是您在搜索和插入函数中看到的内容：前者遍历到 bit 的末尾，而后者遍历到根。

II – Partition recurrence relation（分区递归）

对于分区递归关系，设置i = 0，j = n-1，m =（n-1）/ 2，我们有：

T（0，n-1）= T（0，m）+ T（m + 1，n-1）+ C

现在，子问题 C 可以理解为“找到重要反向对的数量，其中反向对的第一个元素来自左子数组nums [0，m]，而对第二个元素来自右子数组nums [m + 1， n-1]”。

再次对于该子问题，自动满足上述两个条件中的第一个条件。至于第二个条件，我们像往常一样将这种简单的线性扫描算法应用于左（或右）子数组中的每个元素。毫不奇怪，这导致了O（n ^ 2）天真解。

幸运的是，此处的观察成立，左或右子数组中元素的顺序无关紧要，这提示了两个子数组中元素的排序。对两个子数组都进行排序后，可以通过使用所谓的两指针技术在线性时间内找到重要的反向对的数量：一个指向左子数组中的元素，另一个指向右子数组中的元素，由于元素的顺序，两个指针都只会向同一个方向移动。

最后一个问题是，哪种算法最适合对子数组进行排序。由于无论如何我们都需要将数组划分为两半，因此将其调整为Merge-sort是最自然的。支持合并排序的另一点是，上面的搜索过程可以无缝地嵌入到合并阶段。

因此，这是基于合并排序的解决方案，其中函数“ reversePairsSub”将返回子数组nums [l，r]中重要的反向对的总数。两点搜索过程由涉及变量p的嵌套while循环表示，其余则是标准合并算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int reversePairs(int[] nums) {
    return reversePairsSub(nums, 0, nums.length - 1);
}

private int reversePairsSub(int[] nums, int l, int r) {
    if (l >= r) return 0;

    int m = l + ((r - l) >> 1);
    int res = reversePairsSub(nums, l, m) + reversePairsSub(nums, m + 1, r);
    int i = l, j = m + 1, k = 0, p = m + 1;
    int[] merge = new int[r - l + 1];
    while (i <= m) {
        while (p <= r && nums[i] > 2 L * nums[p]) p++;
        res += p - (m + 1);
        while (j <= r && nums[i] >= nums[j]) merge[k++] = nums[j++];
        merge[k++] = nums[i++];
    }
    while (j <= r) merge[k++] = nums[j++];
    System.arraycopy(merge, 0, nums, l, merge.length);
    return res;
}

III – Summary

通过将问题分解为应用于子数组的子问题，然后将解决方案与原始问题和子问题相联系，可以解决许多涉及数组的问题，子问题具有顺序递归关系和分区递归关系。无论哪种情况，识别子问题C并找到有效的算法都至关重要。

如果子问题C涉及在“动态搜索空间”上进行搜索，请尝试考虑在搜索和更新上都支持相对快速操作的数据结构（例如自平衡BST，BIT，段树等）。

如果分区递归关系的子问题C涉及排序，那么Merge-sort将是一个很好的排序算法。同样，如果可以将子问题的解决方案嵌入到合并过程中，则代码可以变得更加优雅。

如果子问题T（i，j）之间有重叠，则最好将中间结果缓存起来，以备将来查找。

最后，让我列举一些属于上述模式的leetcode问题，从而可以用相似的思想来解决。

315. Count of Smaller Numbers After Self

317. Count of Range Sum

对于leetcode 315，应用顺序递归关系（固定为j），子问题C理解为：在访问的元素中找到小于当前元素的元素数量，这涉及在“动态搜索空间”中搜索；应用分区递归关系，我们有一个子问题C：对于左半部分中的每个元素，找到右半部分中小于它的元素数目，注意这些元素正是在合并过程中向左交换的元素，因此可以嵌入到合并过程中。

对于leetcode 327，在先和数组上应用顺序递归关系（固定j），子问题C读取：找到给定范围内被访问元素之外的元素数，这又涉及到搜索“动态搜索空间”;应用分区递归关系，我们有一个子问题C：对于左半部分中的每个元素，找到右半部分中给定范围内的元素数量，可以使用两指针技术将其嵌入到合并过程中。

无论如何，希望这些想法能提高您解决数组相关问题的技巧。