LC-1157. 子数组中占绝大多数的元素（二分查找+随即猜，摩尔投票+线段树，upper_bound和lower_bound函数）

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

难度困难96收藏分享切换为英文接收动态反馈

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

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

统计每个元素的索引-超时

class MajorityChecker {Map<Integer, List<Integer>> map = new HashMap<>();public MajorityChecker(int[] arr) {for(int i = 0; i < arr.length; i++){// 统计每个元素的索引map.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);}}public int query(int left, int right, int threshold) {for(Map.Entry<Integer, List<Integer>> entry : map.entrySet()){List<Integer> indexList = entry.getValue();if(indexList.size() < threshold) continue;int i = lowerBound(indexList, left);int j = upperBound(indexList, right);if(j - i >= threshold) return entry.getKey();}return -1;}   // upper_bound ： 返回大于等于key的最后一个元素下标public int upperBound(List<Integer> list, int target){int left = 0, right = list.size();while(left < right){int mid = (left + right) >> 1;if(list.get(mid) > target) right = mid;else left = mid + 1;}return left;}// lower_bound ： 返回大于等于key的第一个元素下标public int lowerBound(List<Integer> list, int target){int left = 0, right = list.size();while(left < right){int mid = (left + right) >> 1;if(list.get(mid) < target) left = mid + 1;else right = mid;}return left;}
}

二分查找 + 随机猜

https://leetcode.cn/problems/online-majority-element-in-subarray/solutions/1880675/suiji-by-981377660lmt-fw82/

随机概率算法：如果一个区间内确实存在绝对众数，那么我们随机选择一个数，这个数为绝对众数的概率至少是 1/2；我们可以计算出这个数在区间内出现了多少次 (可以预处理+二分 O(logn)求出) 。如果出现频率大于等于 threshold ，那么这个数就是区间的绝对众数；如果随机选择了20次，都没有找到符合条件的数，那么就说明区间内确实不存在绝对众数。

class MajorityChecker {int arr[];List<Integer> idx[]; // 统计元素所有的下标public MajorityChecker(int[] arr) {this.arr = arr;idx = new List[20005];for(int i = 1; i < 20005; i++) idx[i] = new ArrayList<>();for(int i = 0; i < arr.length; i++){idx[arr[i]].add(i);}}public int query(int left, int right, int threshold) {for(int i = 0; i < 30; i++){// 在(left, right)区间内中随机选择一个索引int targetidx = (int)(Math.random() * (right-left + 1) + left);int a = arr[targetidx];//先找最左边int l = lowerBound(idx[a], left);int r = upperBound(idx[a], right);if(r - l >= threshold) return a;}return -1;}// upper_bound ： 返回大于等于key的最后一个元素下标public int upperBound(List<Integer> list, int target){int left = 0, right = list.size();while(left < right){int mid = (left + right) >> 1;if(list.get(mid) > target) right = mid;else left = mid + 1;}return left;}// lower_bound ： 返回大于等于key的第一个元素下标public int lowerBound(List<Integer> list, int target){int left = 0, right = list.size();while(left < right){int mid = (left + right) >> 1;if(list.get(mid) < target) left = mid + 1;else right = mid;}return left;}
}

摩尔投票 + 线段树

不会做

题解：https://leetcode.cn/problems/online-majority-element-in-subarray/solution/sui-ji-tou-piao-xuan-qu-huo-zhe-mo-er-to-etvb/

(1) 首先是看到区间处理，看到区间的计数，就应该联想到线段树的操作，或者说差分数组

(2) 这里对于线段树节点的数值记录，需要记录哪些数值呢？可以联想到数组中众数选取的摩尔投票法则来进行，也就是说线段树节点分别记录两个数值，一个该区间的众数选取真实数值，一个该区间的众数对应的投票数目，这样对于区间合并的时候就可以递推出摩尔投票的方式了

摩尔投票法则:原理就是使用两个变量，一个major记录当前数字，一个count记录当前数字出现的次数，遇到相同的count就加1，遇到不同的就减1，当count小于0的时候，说明前面的都相互抵消完了，major和count都要重新赋值……，最后再判断major是否是主要元素即可。

摩尔投票理解思路：诸侯争霸，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽，且自己人不会彼此内战。最后还有人活下来的国家就是胜利，因为你方人多（超过总人数1半），所以必然是你胜利。实际操作的时候，当candidate不同的时候，count就保留差值即可。

class Node {int l, r;int x, cnt;
}class SegmentTree {private Node[] tr;private int[] nums;public SegmentTree(int[] nums) {int n = nums.length;this.nums = nums;tr = new Node[n << 2];for (int i = 0; i < tr.length; ++i) {tr[i] = new Node();}build(1, 1, n);}private void build(int u, int l, int r) {tr[u].l = l;tr[u].r = r;if (l == r) {tr[u].x = nums[l - 1];tr[u].cnt = 1;return;}int mid = (l + r) >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);pushup(u);}public int[] query(int u, int l, int r) {if (tr[u].l >= l && tr[u].r <= r) {return new int[] {tr[u].x, tr[u].cnt};}int mid = (tr[u].l + tr[u].r) >> 1;if (r <= mid) {return query(u << 1, l, r);}if (l > mid) {return query(u << 1 | 1, l, r);}var left = query(u << 1, l, r);var right = query(u << 1 | 1, l, r);if (left[0] == right[0]) {left[1] += right[1];} else if (left[1] >= right[1]) {left[1] -= right[1];} else {right[1] -= left[1];left = right;}return left;}private void pushup(int u) {if (tr[u << 1].x == tr[u << 1 | 1].x) {tr[u].x = tr[u << 1].x;tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt;} else if (tr[u << 1].cnt >= tr[u << 1 | 1].cnt) {tr[u].x = tr[u << 1].x;tr[u].cnt = tr[u << 1].cnt - tr[u << 1 | 1].cnt;} else {tr[u].x = tr[u << 1 | 1].x;tr[u].cnt = tr[u << 1 | 1].cnt - tr[u << 1].cnt;}}
}class MajorityChecker {private SegmentTree tree;private Map<Integer, List<Integer>> d = new HashMap<>();public MajorityChecker(int[] arr) {tree = new SegmentTree(arr);for (int i = 0; i < arr.length; ++i) {d.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);}}public int query(int left, int right, int threshold) {int x = tree.query(1, left + 1, right + 1)[0];int l = search(d.get(x), left);int r = search(d.get(x), right + 1);return r - l >= threshold ? x : -1;}private int search(List<Integer> arr, int x) {int left = 0, right = arr.size();while (left < right) {int mid = (left + right) >> 1;if (arr.get(mid) >= x) {right = mid;} else {left = mid + 1;}}return left;}
}
//作者：lcbin
//链接：https://leetcode.cn/problems/online-majority-element-in-subarray/solution/python3javacgo-yi-ti-yi-jie-xian-duan-sh-1w39/

剑指 Offer 39. 数组中出现次数超过一半的数字

难度简单368

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制：

1 <= 数组长度 <= 50000

摩尔投票

https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mo-er-tou-piao-shu-zu-zhong-chu-xian-ci-8xbnz/

想象一下，假如数组是一个投票箱，数组元素是一张写了选举人编号的一张选票。

题目要求我们找出哪个数字，超过了数组的一半！

是否就可以想象为，哪个人成为了最终选举的胜利者呢？

那么，接下来我们要做的事情，就是找到票数最多的那个人的编号即可。

是不是感觉像这么回事儿，很好！

我们可以试着模拟一下，如下所示：

假如我们有个职位，需要从 A，B 两位候选人中选出
先抽出一张票，投的是 A，我们在黑板上写着当前胜利者：A，票数：1
再抽出一张票，投的是 A，我们在黑板上写着当前胜利者：A，票数：2
再抽出一张票，投的是 B，用一张 B 抵消一张 A 的选票，我们在黑板上写着当前胜利者：A，票数：1
再抽出一张票，投的是 B，用一张 B 抵消一张 A 的选票，我们在黑板上写着当前胜利者：无，票数：0
再抽出一张票，投的是 A，我们在黑板上写着当前胜利者：A，票数：1
抽取完毕，恭喜 A 获胜，赢得该职位。

经过以上实例分析，我们可以得出 3 个要点：

不同候选人的选票之间，可以一一抵消。

若当前胜利者存在多张选票时，不同的候选人的票，只能抵消一张当前胜利者的票。

若当前双方的选票被抵消为零，下一次抽出的候选人，将作为暂时的胜利者领先。

class Solution {public int majorityElement(int[] nums) {int ans = 0, count = 0;for(int i = 0; i < nums.length; i++){if(count == 0){ans  = nums[i];count++;}else{count += nums[i] == ans ? 1 : -1;}}return ans;}
}

其他

upper_bound和lower_bound函数

Java写法

// upper_bound ： 返回大于等于key的最后一个元素下标
public int upperBound(List<Integer> list, int target){int left = 0, right = list.size();while(left < right){int mid = (left + right) >> 1;if(list.get(mid) > target) right = mid;else left = mid + 1;}return left;
}
// lower_bound ： 返回大于等于key的第一个元素下标
public int lowerBound(List<Integer> list, int target){int left = 0, right = list.size();while(left < right){int mid = (left + right) >> 1;if(list.get(mid) < target) left = mid + 1;else right = mid;}return left;
}