1157. Online Majority Element In Subarray Hard

1/**
2 * [1157] Online Majority Element In Subarray
3 *
4 * Design a data structure that efficiently finds the majority element of a given subarray.
5 * The majority element of a subarray is an element that occurs threshold times or more in the subarray.
6 * Implementing the MajorityChecker class:
7 * 
8 * 	MajorityChecker(int[] arr) Initializes the instance of the class with the given array arr.
9 * 	int query(int left, int right, int threshold) returns the element in the subarray arr[left...right] that occurs at least threshold times, or -1 if no such element exists.
10 * 
11 *  
12 * Example 1:
13 * 
14 * Input
15 * ["MajorityChecker", "query", "query", "query"]
16 * [[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
17 * Output
18 * [null, 1, -1, 2]
19 * Explanation
20 * MajorityChecker majorityChecker = new MajorityChecker([1, 1, 2, 2, 1, 1]);
21 * majorityChecker.query(0, 5, 4); // return 1
22 * majorityChecker.query(0, 3, 3); // return -1
23 * majorityChecker.query(2, 3, 2); // return 2
24 * 
25 *  
26 * Constraints:
27 * 
28 * 	1 <= arr.length <= 2 * 10^4
29 * 	1 <= arr[i] <= 2 * 10^4
30 * 	0 <= left <= right < arr.length
31 * 	threshold <= right - left + 1
32 * 	2 * threshold > right - left + 1
33 * 	At most 10^4 calls will be made to query.
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/online-majority-element-in-subarray/
39// discuss: https://leetcode.com/problems/online-majority-element-in-subarray/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43struct MajorityChecker {
44        false
45    }
46
47
48/** 
49 * `&self` means the method takes an immutable reference.
50 * If you need a mutable reference, change it to `&mut self` instead.
51 */
52impl MajorityChecker {
53
54    fn new(arr: Vec<i32>) -> Self {
55        
56    }
57    
58    fn query(&self, left: i32, right: i32, threshold: i32) -> i32 {
59        
60    }
61}
62
63/**
64 * Your MajorityChecker object will be instantiated and called as such:
65 * let obj = MajorityChecker::new(arr);
66 * let ret_1: i32 = obj.query(left, right, threshold);
67 */
68
69// submission codes end
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test_1157() {
77    }
78}
79