Majority Element II

Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Follow-up: Could you solve the problem in linear time and in O(1) space?

Example 1:

Input: nums = [3,2,3]
Output: [3]

Example 2:

Input: nums = [1]
Output: [1]

Example 3:

Input: nums = [1,2]
Output: [1,2]

Constraints:

• 1 <= nums.length <= 5 * 104

• -109 <= nums[i] <= 109

Solutions

🧠 Cpp

class Solution
{
public:
    vector<int> majorityElement(vector<int>& nums)
    {
        std::map<int, size_t> marks;

        for(auto &num : nums)
            marks[num]++;

        const int limit = nums.size() / 3;
        vector<int> res;

        for(auto &mark : marks)
            if(mark.second > limit)
                res.push_back(mark.first);

        return res;
    }
};