子数组中占绝大多数的元素

难度: Hard

设计一个数据结构，有效地找到给定子数组的 多数元素 。

子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。

实现 MajorityChecker 类:

MajorityChecker(int[] arr) 会用给定的数组 arr 对 MajorityChecker 初始化。
int query(int left, int right, int threshold) 返回子数组中的元素 arr[left...right] 至少出现 threshold 次数，如果不存在这样的元素则返回 -1。

示例 1：

输入:
["MajorityChecker", "query", "query", "query"]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
输出：
[null, 1, -1, 2]

解释：
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

提示：

1 <= arr.length <= 2 * 10⁴
1 <= arr[i] <= 2 * 10⁴
0 <= left <= right < arr.length
threshold <= right - left + 1
2 * threshold > right - left + 1
调用 query 的次数最多为 10⁴

Submission

运行时间: 341 ms

内存: 26.9 MB

class MajorityChecker:
    k = 10

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.loc = defaultdict(list)

        for i, val in enumerate(arr):
            self.loc[val].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        arr_ = self.arr
        loc_ = self.loc
        
        length = right - left + 1
        for i in range(MajorityChecker.k):
            x = arr_[randint(left, right)]
            pos = loc_[x]
            occ = bisect_right(pos, right) - bisect_left(pos, left)
            if occ >= threshold:
                return x
            elif occ * 2 >= length:
                return -1

        return -1

Explain

该题解采用了随机化和二分查找的方法来解决问题。首先，通过遍历数组arr，将每个元素的索引位置存储在一个哈希表loc中。然后在query方法中，随机选择k次数组中的一个元素x，并查找这个元素在子数组[left, right]中出现的次数，使用二分查找来快速计算元素x在子数组中的出现次数。如果x的出现次数大于等于阈值threshold，则返回x；如果x的出现次数大于等于子数组长度的一半，但小于threshold，则说明子数组中不存在多数元素，返回-1。如果k次随机选择都没有找到多数元素，则最终也返回-1。

时间复杂度: O(n + k log n)

空间复杂度: O(n)

class MajorityChecker:
    k = 10

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.loc = defaultdict(list)

        for i, val in enumerate(arr):
            self.loc[val].append(i)

    def query(self, left: int, right: int, threshold: int) -> int:
        arr_ = self.arr
        loc_ = self.loc
        
        length = right - left + 1
        for i in range(MajorityChecker.k):
            x = arr_[randint(left, right)]
            pos = loc_[x]
            occ = bisect_right(pos, right) - bisect_left(pos, left)
            if occ >= threshold:
                return x
            elif occ * 2 >= length:
                return -1

        return -1

Explore

使用哈希表存储每个元素的所有索引位置能够快速地检索任何元素在数组中的所有出现位置。这种数据结构的优势在于其提供了高效的查找、插入和删除操作。在本题中，哈希表使得我们能够在O(1)时间复杂度内访问到任何元素的索引列表，从而支持快速地计算任意子数组中元素的出现次数。这是非常适合需要频繁查询和处理数组中特定元素位置信息的场景。

随机选择元素的方法确实可能导致查询结果的不稳定性，因为每次查询可能选取不同的元素进行检查，从而可能在不同的查询中得到不同的结果。为了评估这种方法的可靠性，可以考虑增加随机选择的次数k，这样可以提高找到多数元素的概率。此外，可以通过实验或理论分析来确定在特定数据分布条件下，选择的k值能够以多大的概率确保结果的准确性。通常，k值的增加会提高算法的稳定性和准确性，但同时也会增加算法的运行时间。

在`query`方法中进行k次随机尝试是为了增加算法找到多数元素的概率。k值的大小直接影响算法的效率和准确性。较大的k值意味着更高的准确性，因为算法有更多机会找到真正的多数元素，但同时也会导致算法运行时间的增加，降低效率。反之，较小的k值可能无法找到多数元素，导致算法准确性下降。因此，选择适当的k值是一种效率与准确性之间的权衡。

二分查找在本题解中用于快速计算某个元素在特定子数组[left, right]中的出现次数。具体方法是：利用二分查找算法，在该元素的索引列表中查找大于等于left的最小位置（通过`bisect_left`）和小于等于right的最大位置（通过`bisect_right`）。两者的位置差即为该元素在子数组中的出现次数。这种方法的优势在于，通过对排序好的索引列表进行二分查找，能够在O(log n)的时间复杂度内完成查找，相比线性搜索大幅提高了效率。