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

力扣链接：1157. 子数组中占绝大多数的元素

题目描述

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

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

实现 MajorityChecker 类:

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

简单来说，就是在MajorityChecker数组中返回query[left，right，次数]的元素。
majorityChecker.query(0,5,4)：查找下表0到5之间出现次数大于等于4次的数字为1，// 返回 1
majorityChecker.query(0,3,3)：查找下表0到3之间出现次数大于等于3次的数字，没有，// 返回 -1

Java代码1

暴力但易懂

class MajorityChecker {private int[] arrays;private int max = 0;public MajorityChecker(int[] arr) {this.arrays = arr;for(int i : arr) {this.max = Math.max(i, max);}}public int query(int left, int right, int threshold) {if(threshold > (right - left + 1)) return -1;int[] flag = new int[max + 1];while(left <= right) {int temp = this.arrays[left];flag[temp]++;if(flag[temp] >= threshold) {return temp;}left++;}return -1;}
}

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/online-majority-element-in-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。