1157. Online Majority Element In Subarray
Description
Design a data structure that efficiently finds the majority element of a given subarray.
The majority element of a subarray is an element that occurs threshold
times or more in the subarray.
Implementing the MajorityChecker
class:
MajorityChecker(int[] arr)
Initializes the instance of the class with the given arrayarr
.int query(int left, int right, int threshold)
returns the element in the subarrayarr[left...right]
that occurs at leastthreshold
times, or-1
if no such element exists.
Example 1:
Input ["MajorityChecker", "query", "query", "query"] [[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]] Output [null, 1, -1, 2] Explanation MajorityChecker majorityChecker = new MajorityChecker([1, 1, 2, 2, 1, 1]); majorityChecker.query(0, 5, 4); // return 1 majorityChecker.query(0, 3, 3); // return -1 majorityChecker.query(2, 3, 2); // return 2
Constraints:
1 <= arr.length <= 2 * 104
1 <= arr[i] <= 2 * 104
0 <= left <= right < arr.length
threshold <= right - left + 1
2 * threshold > right - left + 1
- At most
104
calls will be made toquery
.
Solutions
Solution 1: Segment Tree + Boyer-Moore Voting Algorithm + Binary Search
We notice that the problem requires us to find the possible majority element in a specific interval, so we consider using a segment tree to maintain the candidate majority element and its occurrence in each interval.
We define each node of the segment tree as Node
, each node contains the following attributes:
l
: The left endpoint of the node, the index starts from $1$.r
: The right endpoint of the node, the index starts from $1$.x
: The candidate majority element of the node.cnt
: The occurrence of the candidate majority element of the node.
The segment tree mainly has the following operations:
build(u, l, r)
: Build the segment tree.pushup(u)
: Use the information of the child nodes to update the information of the parent node.query(u, l, r)
: Query the interval sum.
In the initialization method of the main function, we first create a segment tree, and use a hash table $d$ to record all indexes of each element in the array.
In the query(left, right, threshold)
method, we directly call the query
method of the segment tree to get the candidate majority element $x$. Then use binary search to find the first index $l$ in the array that is greater than or equal to $left$, and the first index $r$ that is greater than $right$. If $r - l \ge threshold$, return $x$, otherwise return $-1$.
In terms of time complexity, the time complexity of the initialization method is $O(n)$, and the time complexity of the query method is $O(\log n)$. The space complexity is $O(n)$. Here, $n$ is the length of the array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
|