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 array arr.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.
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 * 1041 <= arr[i] <= 2 * 1040 <= left <= right < arr.lengththreshold <= right - left + 12 * threshold > right - left + 1- At most
104 calls will be made to query.
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
| class Node:
__slots__ = ("l", "r", "x", "cnt")
def __init__(self):
self.l = self.r = 0
self.x = self.cnt = 0
class SegmentTree:
def __init__(self, nums):
self.nums = nums
n = len(nums)
self.tr = [Node() for _ in range(n << 2)]
self.build(1, 1, n)
def build(self, u, l, r):
self.tr[u].l, self.tr[u].r = l, r
if l == r:
self.tr[u].x = self.nums[l - 1]
self.tr[u].cnt = 1
return
mid = (l + r) >> 1
self.build(u << 1, l, mid)
self.build(u << 1 | 1, mid + 1, r)
self.pushup(u)
def query(self, u, l, r):
if self.tr[u].l >= l and self.tr[u].r <= r:
return self.tr[u].x, self.tr[u].cnt
mid = (self.tr[u].l + self.tr[u].r) >> 1
if r <= mid:
return self.query(u << 1, l, r)
if l > mid:
return self.query(u << 1 | 1, l, r)
x1, cnt1 = self.query(u << 1, l, r)
x2, cnt2 = self.query(u << 1 | 1, l, r)
if x1 == x2:
return x1, cnt1 + cnt2
if cnt1 >= cnt2:
return x1, cnt1 - cnt2
else:
return x2, cnt2 - cnt1
def pushup(self, u):
if self.tr[u << 1].x == self.tr[u << 1 | 1].x:
self.tr[u].x = self.tr[u << 1].x
self.tr[u].cnt = self.tr[u << 1].cnt + self.tr[u << 1 | 1].cnt
elif self.tr[u << 1].cnt >= self.tr[u << 1 | 1].cnt:
self.tr[u].x = self.tr[u << 1].x
self.tr[u].cnt = self.tr[u << 1].cnt - self.tr[u << 1 | 1].cnt
else:
self.tr[u].x = self.tr[u << 1 | 1].x
self.tr[u].cnt = self.tr[u << 1 | 1].cnt - self.tr[u << 1].cnt
class MajorityChecker:
def __init__(self, arr: List[int]):
self.tree = SegmentTree(arr)
self.d = defaultdict(list)
for i, x in enumerate(arr):
self.d[x].append(i)
def query(self, left: int, right: int, threshold: int) -> int:
x, _ = self.tree.query(1, left + 1, right + 1)
l = bisect_left(self.d[x], left)
r = bisect_left(self.d[x], right + 1)
return x if r - l >= threshold else -1
# Your MajorityChecker object will be instantiated and called as such:
# obj = MajorityChecker(arr)
# param_1 = obj.query(left,right,threshold)
|
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| 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;
}
}
/**
* Your MajorityChecker object will be instantiated and called as such:
* MajorityChecker obj = new MajorityChecker(arr);
* int param_1 = obj.query(left,right,threshold);
*/
|
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| class Node {
public:
int l = 0, r = 0;
int x = 0, cnt = 0;
};
using pii = pair<int, int>;
class SegmentTree {
public:
SegmentTree(vector<int>& nums) {
this->nums = nums;
int n = nums.size();
tr.resize(n << 2);
for (int i = 0; i < tr.size(); ++i) {
tr[i] = new Node();
}
build(1, 1, n);
}
pii query(int u, int l, int r) {
if (tr[u]->l >= l && tr[u]->r <= r) {
return {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);
}
auto left = query(u << 1, l, r);
auto right = query(u << 1 | 1, l, r);
if (left.first == right.first) {
left.second += right.second;
} else if (left.second >= right.second) {
left.second -= right.second;
} else {
right.second -= left.second;
left = right;
}
return left;
}
private:
vector<Node*> tr;
vector<int> nums;
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);
}
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 {
public:
MajorityChecker(vector<int>& arr) {
tree = new SegmentTree(arr);
for (int i = 0; i < arr.size(); ++i) {
d[arr[i]].push_back(i);
}
}
int query(int left, int right, int threshold) {
int x = tree->query(1, left + 1, right + 1).first;
auto l = lower_bound(d[x].begin(), d[x].end(), left);
auto r = lower_bound(d[x].begin(), d[x].end(), right + 1);
return r - l >= threshold ? x : -1;
}
private:
unordered_map<int, vector<int>> d;
SegmentTree* tree;
};
/**
* Your MajorityChecker object will be instantiated and called as such:
* MajorityChecker* obj = new MajorityChecker(arr);
* int param_1 = obj->query(left,right,threshold);
*/
|
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| type node struct {
l, r, x, cnt int
}
type segmentTree struct {
nums []int
tr []*node
}
type pair struct{ x, cnt int }
func newSegmentTree(nums []int) *segmentTree {
n := len(nums)
tr := make([]*node, n<<2)
for i := range tr {
tr[i] = &node{}
}
t := &segmentTree{nums, tr}
t.build(1, 1, n)
return t
}
func (t *segmentTree) build(u, l, r int) {
t.tr[u].l, t.tr[u].r = l, r
if l == r {
t.tr[u].x = t.nums[l-1]
t.tr[u].cnt = 1
return
}
mid := (l + r) >> 1
t.build(u<<1, l, mid)
t.build(u<<1|1, mid+1, r)
t.pushup(u)
}
func (t *segmentTree) query(u, l, r int) pair {
if t.tr[u].l >= l && t.tr[u].r <= r {
return pair{t.tr[u].x, t.tr[u].cnt}
}
mid := (t.tr[u].l + t.tr[u].r) >> 1
if r <= mid {
return t.query(u<<1, l, r)
}
if l > mid {
return t.query(u<<1|1, l, r)
}
left, right := t.query(u<<1, l, r), t.query(u<<1|1, l, r)
if left.x == right.x {
left.cnt += right.cnt
} else if left.cnt >= right.cnt {
left.cnt -= right.cnt
} else {
right.cnt -= left.cnt
left = right
}
return left
}
func (t *segmentTree) pushup(u int) {
if t.tr[u<<1].x == t.tr[u<<1|1].x {
t.tr[u].x = t.tr[u<<1].x
t.tr[u].cnt = t.tr[u<<1].cnt + t.tr[u<<1|1].cnt
} else if t.tr[u<<1].cnt >= t.tr[u<<1|1].cnt {
t.tr[u].x = t.tr[u<<1].x
t.tr[u].cnt = t.tr[u<<1].cnt - t.tr[u<<1|1].cnt
} else {
t.tr[u].x = t.tr[u<<1|1].x
t.tr[u].cnt = t.tr[u<<1|1].cnt - t.tr[u<<1].cnt
}
}
type MajorityChecker struct {
tree *segmentTree
d map[int][]int
}
func Constructor(arr []int) MajorityChecker {
tree := newSegmentTree(arr)
d := map[int][]int{}
for i, x := range arr {
d[x] = append(d[x], i)
}
return MajorityChecker{tree, d}
}
func (this *MajorityChecker) Query(left int, right int, threshold int) int {
x := this.tree.query(1, left+1, right+1).x
l := sort.SearchInts(this.d[x], left)
r := sort.SearchInts(this.d[x], right+1)
if r-l >= threshold {
return x
}
return -1
}
/**
* Your MajorityChecker object will be instantiated and called as such:
* obj := Constructor(arr);
* param_1 := obj.Query(left,right,threshold);
*/
|
