题目描述：
Implementing the class
MajorityChecker, which has the following API:MajorityChecker(int[] arr)constructs an instance of MajorityChecker with the given arrayarr;int query(int left, int right, int threshold)has arguments such that:0 <= left <= right < arr.lengthrepresenting a subarray ofarr;2 * threshold > right - left + 1, ie. the threshold is always a strict majority of the length of the subarray
Each
query(...) returns the element in arr[left], arr[left+1], ..., arr[right] that occurs at least threshold times, or -1 if no such element exists.
Example:
MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]); majorityChecker.query(0,5,4); // returns 1 majorityChecker.query(0,3,3); // returns -1 majorityChecker.query(2,3,2); // returns 2
Constraints:
1 <= arr.length <= 200001 <= arr[i] <= 20000- For each query,
0 <= left <= right < len(arr) - For each query,
2 * threshold > right - left + 1 - The number of queries is at most
10000
1. Moore Voting Solution
这个解法不是第一次出现在Leetcode，我第一次使用这个算法是在 [Majority Element](https://leetcode.com/problems/majority-element/) 中。
class MajorityChecker {
int[] arr;
public MajorityChecker(int[] arr) {
this.arr = arr;
}
public int query(int left, int right, int threshold) {
int cnt = 0, val = -1;
// voting algo
for(int i = left; i <= right; i++) {
if(cnt == 0) {
cnt++;
val = arr[i];
} else {
if(arr[i] == val)
cnt++;
else
cnt--;
}
}
// check whether the winner is larger or equal to threshold
cnt = 0;
for(int i = left; i <= right; i++) {
if(val == arr[i])
cnt++;
}
if(cnt >= threshold)
return val;
else
return -1;
}
}
2. 近似算法
假设我们要计算[l, r]中majority元素，如果这个数字存在，我们随机选择一个数字，那么这个数字就是majority元素的概率至少是1/2。如果我们重复20次，那么我们没有选择到majority元素的概率是 (1/2）^20，这个是非常小的概率。我们利用这个近似的算法来计算。那么问题变成了已知l,r且对于一个随机选择的val，怎么才能高效判断这个val是不是majority元素呢，我们可以二分搜索。代码如下：
class MajorityChecker {
// store val -> set of idx
Map<Integer, List<Integer>> map;
Random random;
int[] arr;
public MajorityChecker(int[] arr) {
map = new HashMap<>();
random = new Random();
for(int i = 0; i < arr.length; i++) {
int val = arr[i];
if(!map.containsKey(val)) {
List<Integer> list = new ArrayList<>();
map.put(val, list);
}
map.get(val).add(i);
}
this.arr = arr;
}
public int query(int left, int right, int threshold) {
for(int times = 0; times < 20; times++) {
int num = random.nextInt(right - left + 1);
int idx = left + num;
int val = arr[idx];
int start = Collections.binarySearch(map.get(val), left);
if(start < 0) start = -(start + 1);
int end = Collections.binarySearch(map.get(val), right);
if(end < 0) end = -(end + 1) - 1;
if(end - start + 1 >= threshold)
return val;
}
return -1;
}
}
3. segment tree
提到线段的题目，经典算法包括BIT和segment tree。 BIT多用于计算某一线段的元素之和，segment tree适用场景比较多。所以直觉上这个题目应该可以使用segment tree来解。这个解法还是用到了上面提到的二分搜索算法。
class MajorityChecker {
int[] data, tree;
Map<Integer, List<Integer>> map;
public MajorityChecker(int[] arr) {
this.data = arr;
tree = new int[arr.length * 4];
map = new HashMap<>();
for(int i = 0; i < arr.length; i++) {
if(!map.containsKey(arr[i])) {
List<Integer> list = new ArrayList<>();
map.put(arr[i], list);
}
map.get(arr[i]).add(i);
}
buildTree(0, arr.length-1, 0);
}
private void buildTree(int start, int end, int treeIdx) {
if(start == end) {
tree[treeIdx] = data[start];
return;
}
int leftTreeIdx = treeIdx * 2 + 1, rightTreeIdx = treeIdx * 2 + 2;
int mid = (start + end) / 2;
buildTree(start, mid, leftTreeIdx);
buildTree(mid+1, end, rightTreeIdx);
if(tree[leftTreeIdx] != 0 && getOccurrence(tree[leftTreeIdx], start, end) * 2 > end - start + 1) {
tree[treeIdx] = tree[leftTreeIdx];
} else if(tree[rightTreeIdx] != 0 && getOccurrence(tree[rightTreeIdx], start, end) * 2 > end - start + 1) {
tree[treeIdx] = tree[rightTreeIdx];
}
}
private int[] query(int treeIdx, int left, int right, int targetL, int targetR) {
if(left >= targetL && right <= targetR) {
if(tree[treeIdx] == 0)
return new int[]{0, 0};
return new int[] {tree[treeIdx], getOccurrence(tree[treeIdx], targetL, targetR)};
}
int mid = (left + right) / 2, leftTreeIdx = treeIdx * 2 + 1, rightTreeIdx = treeIdx * 2 + 2;
if(targetL > mid)
return query(rightTreeIdx, mid+1, right, targetL, targetR);
else if (targetR <= mid)
return query(leftTreeIdx, left, mid, targetL, targetR);
else {
int[] ans1 = query(leftTreeIdx, left, mid, targetL, targetR);
if(ans1[0] > 0 && ans1[1] * 2 > targetR - targetL + 1) return ans1;
int[] ans2 = query(rightTreeIdx, mid+1, right, targetL, targetR);
if(ans2[0] > 0) return ans2;
return new int[] {0, 0};
}
}
private int getOccurrence(int num, int left, int right) {
List<Integer> list = map.get(num);
int start = Collections.binarySearch(list, left);
if(start < 0) start = -(start + 1);
int end = Collections.binarySearch(list, right);
if(end < 0) end = -(end + 1) - 1;
return end - start + 1;
}
public int query(int left, int right, int threshold) {
int[] ans = query(0, 0, data.length-1, left, right);
if(ans[1] >= threshold) return ans[0];
return -1;
}
}
TAKE AWAY POINTS:
- Moore Voting Algo
- Segment Tree
- Random API -> random.nextInt(100) 会生成0-99数字
