题目描述：
设计一个数据结构，有效地找到给定子数组的多数元素，子数组的多数元素是在子数组中出现threshold次及以上的元素。
实现MajorityChecker类：
MajorityChecker(int[] arr)会用给定鹅数组对类初始化。int query(int left, int right, int threshold)返回子数组中至少出现threshold次的元素，如果不存在则返回-1。
数据范围：
$1\le arr.length\le 2\times 10^4,1\le arr[i]\le 2\times 10^4$
$2\times threshold\gt right-left + 1, 1\le q \le 10^4$
题解：
随机化+二分搜索：
对一段区间 $[l,r]$ 中的元素，随机选择 $k$ 次，每次都是独立重复实验，并且因为 $threshold$ 大小超过区间长度的一半，因此每次询问得到正确答案的概率为：
总共有 $q$ 次询问，全正确的概率为：
当 $k$ 取 $20$ 时， $P \gt 99\%$ ，当 $k$ 取 $30$ 时， $P \gt 99.999\%$
线段树+摩尔投票
代码：
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return 0;
}();
class MajorityChecker
{
public:
vector<vector<int>> pos;
default_random_engine gen;
vector<int> arr;
MajorityChecker(vector<int> &arr) : arr(arr)
{
int n = arr.size();
pos.resize(n + 1);
for (int i = 0; i < n; ++i)
{
pos[arr[i]].emplace_back(i);
}
}
int query(int left, int right, int threshold)
{
uniform_int_distribution<int> dis(left, right);
int length = right - left + 1;
for (int i = 0, index, times; i < 30; ++i)
{
index = arr[dis(gen)];
times = upper_bound(pos[index].begin(), pos[index].end(), right) - lower_bound(pos[index].begin(), pos[index].end(), left);
if (times >= threshold)
{
return index;
}
else if (times * 2 >= length)
{
return -1;
}
}
return -1;
}
};
|