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
| class MajorityChecker {
static final int K = 20;
int[] arr;
Map<Integer, List<Integer>> loc;
Random random;
public MajorityChecker(int[] arr) {
this.arr = arr;
this.loc = new HashMap<>();
for (int i = 0; i < arr.length; ++i) {
loc.putIfAbsent(arr[i], new ArrayList<>());
loc.get(arr[i]).add(i);
}
this.random = new Random();
}
public int query(int left, int right, int threshold) {
int length = right - left + 1;
for (int i = 0; i < K; ++i) {
int x = arr[left + random.nextInt(length)];
List<Integer> pos = loc.get(x);
int cnt = searchEnd(pos, right) - searchStart(pos, left);
if (cnt >= threshold) {
return x;
} else if (cnt * 2 >= length) {
return -1;
}
}
return -1;
}
private int searchStart(List<Integer> pos, int target) {
int low = 0, high = pos.size();
while (low < high) {
int mid = low + (high - low) / 2;
if (pos.get(mid) >= target) high = mid;
else low = mid + 1;
}
return low;
}
private int searchEnd(List<Integer> pos, int target) {
int low = 0, high = pos.size();
while (low < high) {
int mid = low + (high - low) / 2;
if (pos.get(mid) > target) high = mid;
else low = mid + 1;
}
return low;
}
}
|
wechat
