题目描述

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

• MajorityChecker(int[] arr)会用给定的数组 arr来构造一个 MajorityChecker 的实例。
• int query(int left, int right, int threshold)有这么几个参数：
  • 0 <= left <= right < arr.length 表示数组arr的子数组的长度。
  • 2 * threshold > right - left + 1，也就是说阈值 threshold始终比子序列长度的一半还要大。
    每次查询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

提示

• 1 <= arr.length <= 20000
• 1 <= arr[i] <= 20000
• 对于每次查询，0 <= left <= right < len(arr)
• 对于每次查询，2 * threshold > right - left + 1
• 查询次数最多为 10000

算法1

(摩尔投票) 实例化: $O(1)$, 查询$O(n)$ (n为查询长度)

由于threshold严格大于查询区间长度的一半, 所以我们可以先用摩尔投票法求出majority element, 再遍历整个区间求出 majority element 个数并判断是否 >= threshold.

关于摩尔投票请参见:
AcWing 52. 数组中出现次数超过一半的数字
Boyer–Moore majority vote algorithm

Java 代码

class MajorityChecker {
    int[] arr;

    public MajorityChecker(int[] arr) {
        this.arr = arr;
    }

    public int query(int left, int right, int threshold) {

        int res = -1;
        int count = 0;

        for (int i = left; i <= right; i++) {
            if (count == 0) {
                res = arr[i];
                count++;
            }
            else {
                if (arr[i] == res) count ++;
                else count--;
            }
        }

        count = 0;

        for (int i = left; i <= right; i++) {
            if (arr[i] == res) count++;
        }

        return count >= threshold ? res : -1;
    }
}

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