题目大意：
子数组中占绝大多数的元素
实现一个 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); // returns 1 majorityChecker.query(0,3,3); // returns -1 majorityChecker.query(2,3,2); // returns 2
提示：
- 1 <= arr.length <= 20000
- 1 <= arr[i] <= 20000
- 对于每次查询，0 <= left <= right < len(arr)
- 对于每次查询，2 * threshold > right – left + 1
- 查询次数最多为 10000
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1157
解题思路分析：
这道题我想到了使用摩尔投票算法，关于该算法可以参考我之前的文章，LEETCODE 169. Majority Element 解题思路分析 。参考完之后，本题可以用来练手，因为几乎是同样的套路。唯一不同的是，本题所给出的区间内并不一定存在多数元素，因此，通过摩尔投票算法取得了一个准多数元素之后，需要再遍历一遍数组，查看该数的出现次数是否大于总数的一半即可。
实现代码：
int[] mArr;
public MajorityChecker(int[] arr) {
mArr=arr;
}
public int query(int left, int right, int threshold) {
int num=-1;
int count=0;
// 摩尔投票
for(int i=left;i<=right;i++){
if(count==0){
num=mArr[i];
count=1;
}else{
if(num==mArr[i]) count++;
else count--;
}
}
count=0;
for(int i=left;i<=right;i++){
if(mArr[i]==num) count++;
}
return count>=threshold?num:-1;
}本题解法执行时间为1117ms。
Runtime: 1117 ms, faster than 26.55% of Java online submissions for Online Majority Element In Subarray.
Memory Usage: 67.4 MB, less than 100.00% of Java online submissions for Online Majority Element In Subarray.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1157-online-majority-element-in-subarray-解题思路分析/