LC 493. Reverse Pairs

https://leetcode.com/problems/reverse-pairs/

之所以想写这题,主要是因为自己在上面做了很多种尝试,虽然这些尝试在时间复杂度面前都是无效的。

LC上只要你的时间复杂度是错的,那么基本上就是TLE,没有办法在代码层面或者是特殊case上优化来AC. 说说这道题目我试过的算法吧。


首先我觉得这个问题是一个线段树,树节点定义如下:

class Tree:
    def __init__(self, se, max_value, min_value):
        self.se = se
        self.max_value = max_value
        self.min_value = min_value
        self.left = None
        self.right = None

如果我们想查询从 `idx` 开始到数组结尾有多少个值是 `<=v` 的话,可以使用下面过程:

def query_tree(t: Tree, idx, v, ctx):
    if t is None:
        return 0
    (s, e) = t.se
    sz = (e - s) + 1
    if idx <= s and v >= t.max_value:
        return sz
    if t.min_value > v:
        return 0

    m = (s + e) // 2
    if idx > m:
        a = 0
    else:
        a = query_tree(t.left, idx, v, ctx)
    b = query_tree(t.right, idx, v, ctx)
    return a + b

上面这段搜索代码要求搜索范围是一边固定(搜索到数组结尾)一边可变,但是改成两边可变的范围也不是什么难事。

这样整个外围代码就是这样的

# note(yan): 不知道这种区间树是否正确足够高效
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        if len(nums) < 2: return 0
        t = build_tree(nums, 0, len(nums) - 1)
        ans = 0
        for i in range(len(nums) - 1):
            j = i + 1
            max_exp = (nums[i] - 1) // 2
            res = query_tree(t, j, max_exp)
            ans += res
        return ans

但是搜索线段树远没有我想像的那么高效,因为这个强烈取决于里面的值分布。如果你运气好,访问第一棵树就可以停止, 如果运气不好,那么就需要搜索整棵树了,访问节点的数量就是线性的。这样下来最坏情况还是O(n^2).

但是我忽视这个时间复杂度,尝试继续从代码上或者是特殊路径上做优化,是否可以避免最坏的情况呢?一个优化点是这样的。

考虑数组 `[10 10 9(X) 4 9(Y) 4 4 4 4 3]` 如果我们从后向前遍历,当我们知道9(Y)后面有5个满足条件点的话, 那么当访问9(X)的话,其实只需要判断两个点 `[4 9(Y)]`, 而其余后面的点肯定是都满足的。

建立这个索引不复杂,时间空间复杂度都是O(n). 这个优化上了之后依然是TLE, 因为这个优化同样很依赖数据的分布。 比如对于 `[8 7 6 5 4 3 2 1]` 没有任何优化效果。


当意识到这个方向走不下去的时候,最好的方法还是从头思考问题,把原来的一些想法全部丢弃掉。如果我们考虑从后往前遍历, 每看到一个点就将这个点保存到数据库S中,我们还是有办法立刻查询到 "在这个数据库S中,有多少个点它的值是小于某个值v的". 我们可以很容易地想到使用二叉树当这个数据库,这样程序大体框架就是这样的了。

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        if len(nums) < 2: return 0
        t = None
        ans = 0
        for i in reversed(range(len(nums))):
            v = nums[i]
            max_exp = (v - 1) // 2
            ans += query_tree(t, max_exp)
            t = insert_tree(t, v)
        return ans

不过简单的二叉树还是不能避免顺序数组造成的最坏情况,所以最好配合AVL来保持平衡。虽然这样的确可以通过,但是时间也比较长, 最重要的是代码也非常多。 *肯定有比AVL更好的方法,LC肯定不会让你去手写旋转树的*。如果要写旋转树,一定就是还有更好的方法。


最后就是使用归并排序算法。归并排序算法时间复杂度有保障,可以处理任何数据分布。而且根据我的经验,很适合解决这类需要重复扫描区间的计数问题。

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.ans = 0  # 直接把全局变量记在这里

        def msort(lst):
            n = len(lst)
            if n <= 1:
                return lst
            return merge(msort(lst[:n // 2]), msort(lst[n // 2:]))

        def merge(a, b):
            i, j = 0, 0
            while i < len(a) and j < len(b):
                if a[i] <= 2 * b[j]:
                    i += 1
                else:
                    self.ans += len(a) - i
                    j += 1
            return sorted(a + b)

        msort(nums)
        return self.ans