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

题目

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

---

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

子数组的 多数元素 是在子数组中出现 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^4
• 1 <= arr[i] <= 2 * 10^4
• 0 <= left <= right < arr.length
• threshold <= right - left + 1
• 2 * threshold > right - left + 1
• 调用 query 的次数最多为 10^4

题解

方法一：

思路

随机采样法

对于区间[l,r]，随机选取其中一个数，这个数如果不是多数元素，说明出现的次数小于区间大小的一半，抽到这样的元素概率是小于0.5的（threshold必定大于区间大小的一半），如果我们抽取k次，每次都保证抽到的不是多数元素的概率是小于$\frac{1}{2^k}$，可见概率是随k增长而指数下降的，k如果取30，那么抽不到多数元素的概率几乎为0。

查询的次数有$10^4$，我们每次查询只需要抽样30次左右，每次抽样需要确定所抽取元素是否为多数元素，常规的办法就是遍历区间统计个数。但这样会超时。

可以将每个元素出现的下标记录到数组，然后二分区间的端点得到区间内有多少下标。

本题如果可以离线的话可以用莫队算法。

代码

class MajorityChecker {
public:
    vector<int> mp[20004];
    vector<int> arr;
    MajorityChecker(vector<int>& arr): arr(arr) {
        for (int i=0; i<arr.size(); i++) {
            mp[arr[i]].push_back(i);
        }
    }
    
    int query(int left, int right, int threshold) {
        for (int i=0; i<20; i++) {
            int v = arr[rand()%(right-left+1)+left];
            auto& a = mp[v];
            int l = lower_bound(a.begin(), a.end(), left)-a.begin();
            int r = upper_bound(a.begin(), a.end(), right)-a.begin();
            if (r-l >= threshold) return v;
        }
        return -1;
    }
};

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * MajorityChecker* obj = new MajorityChecker(arr);
 * int param_1 = obj->query(left,right,threshold);
 */