題目： LeetCode - 229. Majority Element II

題目說明

給一個陣列，求陣列中出現次數大於 陣列大小 / 3 的元素。

解題思路

先使用 Unordered_map 紀錄每個元素出現的次數，接著遍歷找出符合條件的元素即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums)
    {
        int bound = nums.size() / 3;
        vector<int> ret;
        unordered_map<int, int> cnt;
        for(auto num : nums) ++cnt[num];
        for(auto& [num, times] : cnt) if(times > bound) ret.emplace_back(num);
        return ret;
    }
};