[LeetCode] 1157. Online Majority Element In Subarray

[grandyang]

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.

这道题让设计一种数据结构可以有效的找出给定范围内子数组的多数，这里还给了一个阈值 threshold，只要出现次数大于等于这个阈值就算是多数。可能有些人看到这里就说，那还不简单么，遍历这个子数组区间，累加每个数字出现的次数呗，大于 threshold 就返回呗。如果就这么简单的话怎么对得起这道题 Hard 的身价，当然是不行的，得另寻更高效的解决方法。既然这里需要统计相同数字出现的次数，有一种以空间换时间的方法就是建立每个数字和其在原数组中出现的所有位置坐标组成的数组的映射，这样做的好处是可以快速知道任意一个数字出现的所有位置，而且坐标还是从小到大有序的，为之后的二分搜索法提供了条件。查找的时候遍历所有的数字，此时有了该数字在数组中出现的所有按顺序排列的坐标，可以用二分法查找第一个不小于左边界 left 的位置，然后再用二分法查找第一个大于右边界 right 的位置，若二者的差值大于等于 threshold，则说明该数字在区间 [left, right] 内至少出现了 threshold 次，返回该数字即可，否则返回 -1，参见代码如下：

解法一：

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;
};

再来看一种优化方法，这里不是按照次数由多到少来选，而是用一种随机的取数方法，由于多数出现的个数是超过一半的，所以随机抽取一个数字是多数的概率是超过 50% 的，那么连续抽多次，不中的概率就变得非常非常小，可以忽略不计，这里将次数设置为 10 就可以了，除了随机选数这部分，剩余的跟之前的就没什么区别了，参见代码如下：

解法三：

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 同步地址:

#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

https://leetcode.com/problems/online-majority-element-in-subarray/discuss/356227/C%2B%2B-Codes-of-different-approaches-(Random-Pick-Trade-off-Segment-Tree-Bucket)

LeetCode All in One 题目讲解汇总(持续更新中...)