# 1157. Online Majority Element In Subarray

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 * 104`
• `1 <= arr[i] <= 2 * 104`
• `0 <= left <= right < arr.length`
• `threshold <= right - left + 1`
• `2 * threshold > right - left + 1`
• At most `104` calls will be made to `query`.

``````class MajorityChecker {
public:
MajorityChecker(vector<int>& arr) {
for (int i = 0; i < arr.size(); ++i) {
idxMap[arr[i]].push_back(i);
}
}

int query(int left, int right, int threshold) {
for (auto &a : idxMap) {
if (a.second.size() < threshold) continue;
auto it1 = lower_bound(begin(a.second), end(a.second), left);
auto it2 = upper_bound(begin(a.second), end(a.second), right);
if (it2 - it1 >= threshold) return a.first;
}
return -1;
}

private:
unordered_map<int, vector<int>> idxMap;
};
``````

``````class MajorityChecker {
public:
MajorityChecker(vector<int>& arr) {
unordered_map<int, vector<int>> idxMap;
for (int i = 0; i < arr.size(); ++i) {
idxMap[arr[i]].push_back(i);
}
for (auto &a : idxMap) idxVec.push_back({a.first, a.second});
sort(begin(idxVec), end(idxVec), [](auto &a, auto &b) {return a.second.size() > b.second.size();});
}

int query(int left, int right, int threshold) {
for (auto &a : idxVec) {
if (a.second.size() < threshold) continue;
auto it1 = lower_bound(begin(a.second), end(a.second), left);
auto it2 = upper_bound(begin(a.second), end(a.second), right);
if (it2 - it1 >= threshold) return a.first;
}
return -1;
}

private:
vector<pair<int, vector<int>>> idxVec;
};
``````

``````class MajorityChecker {
public:
MajorityChecker(vector<int>& arr) {
for (int i = 0; i < arr.size(); ++i) {
idxMap[arr[i]].push_back(i);
}
nums = arr;
}

int query(int left, int right, int threshold) {
for (int i = 0; i < 10; ++i) {
auto a = idxMap.find(nums[left + rand() % (right - left + 1)]);
if (a->second.size() < threshold) continue;
auto it1 = lower_bound(begin(a->second), end(a->second), left);
auto it2 = upper_bound(begin(a->second), end(a->second), right);
if (it2 - it1 >= threshold) return a->first;
}
return -1;
}

private:
vector<int> nums;
unordered_map<int, vector<int>> idxMap;
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1157

https://leetcode.com/problems/online-majority-element-in-subarray/

https://leetcode.com/problems/online-majority-element-in-subarray/discuss/356108/C%2B%2B-160-ms-frequency-%2B-binary-search