*子数组中占绝大多数的元素【LC1157】
设计一个数据结构，有效地找到给定子数组的 多数元素 。
子数组的 多数元素 是在子数组中出现
threshold次数或次数以上的元素。实现
MajorityChecker类:
MajorityChecker(int[] arr)会用给定的数组arr对MajorityChecker初始化。int query(int left, int right, int threshold)返回子数组中的元素arr[left...right]至少出现threshold次数，如果不存在这样的元素则返回-1。
第一次做线段树 又被难到
- 思路
需要求解的问题有两个：找出 可能的 绝对众数和统计这个数出现的次数 - 由于题目中
2 * threshold > right - left + 1，因此可以得出结论：每次查询时不一定存在多数元素，但存在多数元素的话找到的一定是多数元素）
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]; return left; } else if (left[1] >= right[1]) {// 值不相等，返回次数较大值，次数为较大值次数-较小值次数 （因为如果相等那么表示，一定不存在多数元素）【不减直接返回也可以通过】 // left[1] -= right[1]; return left; } else { return right; // right[1] -= left[1]; // left = right; } } // 更新节点信息 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);// 原数组中下标小于left的x的个数 int r = search(d.get(x), right + 1);// 原数组中下标小于right + 1的x的个数 // 相减即为区间[l,r]中x的个数 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; } }
