【每日一题Day179】LC1157子数组中占绝大多数的元素 | 线段树

*子数组中占绝大多数的元素【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，因此可以得出结论：每次查询时不一定存在多数元素，但存在多数元素的话找到的一定是多数元素）
  • 而某个区间的多数元素，符合区间加法，区间$[L,R]$的多数元素一定是区间$[L,M]$和区间$[M+1,R]$的多数元素中的其中一个，因此可以使用线段树的方式解决该问题
  • 需要注意的是，通过线段树查找到的$x$只是可能的多数元素（摩尔投票），是否真的是答案，需要通过二分查找判断：记录每个数字出现的索引，找到 x在数组中第一个大于等于 left的下标 l，以及第一个大于 righ的下标 r。如果 r−l≥threshold，则返回 x，否则返回 −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;}
  }
  

  • 复杂度
    • 时间复杂度：初始化时间复杂度为$O(n)$，查询复杂度为$O(logn)$
    • 空间复杂度：$O(n)$