Leetcode 1157:子数组中占绝大多数的元素(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1157:子数组中占绝大多数的元素(超详细的解法!!!)

in leetcode with 0 comment

实现一个 MajorityChecker 的类,它应该具有下述几个API

每次查询 query(...) 会返回在 arr[left], arr[left+1], ..., arr[right] 中至少出现阀值次数 threshold 的元素,如果不存在这样的元素,就返回 -1

示例:

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // 返回 1
majorityChecker.query(0,3,3); // 返回 -1
majorityChecker.query(2,3,2); // 返回 2 

提示:

解题思路

首先不难想到暴力法,也就是对每次的query统计区间内的元素个数,找到最多的那个即可。

class MajorityChecker:
    def __init__(self, arr: List[int]):
        self.data = arr
        
    def query(self, left: int, right: int, threshold: int) -> int:
        data = collections.Counter(self.data[left:right+1])
        t = sorted(data.items(), key=lambda a : a[1])
        if t[-1][1] >= threshold:
            return t[-1][0]
        return -1

对于求众数的过程我们也可以通过摩尔投票算法,但是总的算法时间复杂度不变。

我们仔细观察这个问题,不难发现这实际上是一个查找问题,也就是查找区间内出现最多的元素x的个数。我们可以建立一个数组存放元素出现的位置,例如1出现的位置

0 1 4 5

对于任意需要查找的区间[left,right]来说,我们可以通过lower_boundupper_bound(二分法)找到上面数组中leftright对应的位置,那么区间中的x个数,就是二者的位置之差。

那么现在的问题难点就在于如何找到区间中的众数是谁?我们可以通过暴力的方法去做,但是需要添加一下优化。我们可以随机的从[left,right]中找一个数来尝试,我们最多尝试k次,这个k更具运气调整O(∩_∩)O哈哈~。假如x是区间中的众数的话,那么选中它的概率就大于$\frac{1}{2}$,那么选10次都选不中的概率就小于$\frac{1}{2^{10}}$。

class MajorityChecker:
    def __init__(self, arr: List[int]):
        self.indexs = collections.defaultdict(list)
        for i, n in enumerate(arr):
            self.indexs[n].append(i)
        self.data = arr

    def query(self, left: int, right: int, threshold: int) -> int:
        for _ in range(6):
            x = self.data[random.randint(left, right)]
            if bisect.bisect_right(self.indexs[x], right) - bisect.bisect_left(self.indexs[x], left) >= threshold:
                return x
        return -1

实际测试的过程中,我使用x=6就通过了。^_^

这个问题还有一个比较正统的做法,就是使用线段树来做。我们树中的节点需要保存两个元素一个是当前区间最多的元素,另一个是得分(就是摩尔投票法中的栈空间大小)。

另外我们需要保存所有元素对应的位置信息(存放到一个列表中),这样我们可以通过线段树找到一个区间内最多的元素是谁,我们可以通过lower_boundupper_bound(二分法)找到上面列表中leftright对应的位置,那么区间中的x个数,就是二者的位置之差。

class MajorityChecker:
    def __init__(self, arr: List[int]):
        self.data = arr
        self.indexs = collections.defaultdict(list)
        for i, v in enumerate(arr):
            self.indexs[v].append(i)
        self.tree = [[0, 0] for _ in range(4*len(arr))]
        if self.data:
            self.buildSegmentTree(0, 0, len(arr) - 1)
            
    def buildSegmentTree(self, treeIndex, l, r):
        if l == r:
            self.tree[treeIndex][0] = self.data[l]
            self.tree[treeIndex][1] = 1
            return 
        
        lc, rc = 2 * treeIndex + 1, 2 * (treeIndex + 1)
        mid = l + r >> 1
        self.buildSegmentTree(lc, l, mid)
        self.buildSegmentTree(rc, mid + 1, r)
        if self.tree[lc][0] == self.tree[rc][0]:
            self.tree[treeIndex][0] = self.tree[lc][0]
            self.tree[treeIndex][1] = self.tree[rc][1] + self.tree[lc][1]
        elif self.tree[lc][1] < self.tree[rc][1]:
            self.tree[treeIndex][0] = self.tree[rc][0]
            self.tree[treeIndex][1] = self.tree[rc][1] - self.tree[lc][1]
        else:
            self.tree[treeIndex][0] = self.tree[lc][0]
            self.tree[treeIndex][1] = self.tree[lc][1] - self.tree[rc][1]

    def query(self, left: int, right: int, threshold: int) -> int:
        res = self._query(0, 0, len(self.data)-1, left, right)[0]
        
        if bisect.bisect_right(self.indexs[res], right) - bisect.bisect_left(self.indexs[res], left) < threshold:
            return -1
        return res
        
    def _query(self, treeIndex, l1, r1, l2, r2):
        if l1 == l2 and r1 == r2:
            return self.tree[treeIndex]
        mid = l1 + r1 >> 1
        lc, rc = 2 * treeIndex + 1, 2 * (treeIndex + 1)
        if r2 <= mid:
            return self._query(lc, l1, mid, l2, r2)
        if l2 > mid:
            return self._query(rc, mid + 1, r1, l2, r2)
        l, r = self._query(lc, l1, mid, l2, mid), self._query(rc, mid + 1, r1, mid + 1, r2)
        
        res = [0, 0]
        if l[0] == r[0]:
            res[0] = l[0]
            res[1] = l[1] + r[1]
        elif l[1] < r[1]:
            res[0] = r[0]
            res[1] = r[1] - l[1]
        else:
            res[0] = l[0]
            res[1] = l[1] - r[1]
        return res

注意体会上面的两个节点合并的过程。

reference:

https://leetcode.com/problems/online-majority-element-in-subarray/discuss/355848/Python-Binary-Search-%2B-Find-the-Majority-Element

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses