Skip to content

0229. 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

Anaysis

This problem is an extension to the Majority Element.

https://leetcode.com/problems/majority-element-ii/discuss/63520/Boyer-Moore-Majority-Vote-algorithm-and-my-elaboration/112881

  1. there are no elements that appear more than n/3 times, then whatever the algorithm got from 1st round would be rejected in the second round.
  2. there is only one element that appears more than n/3 times, after 1st round one of the candidates must be that appears more than n/3 times(<2n/3 other elements could only pair out for <n/3 times), the other candidate is not necessarily the second most frequent but it would be rejected in 2nd round.
  3. there are two elements that appear more than n/3 times, candidates would contain both of them. (<n/3 other elements couldn't pair out any of the majorities.)

Code

class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            vector<int> res;
            int a = 0, b = 0, cnt1 = 0, cnt2 = 0, n = nums.size();
            for (int num : nums) {
                if (num == a) {
                    ++cnt1; 
                } else if (num == b) {
                    ++cnt2; 
                } else if (cnt1 == 0) {
                    a = num;
                    cnt1 = 1;
                } else if (cnt2 == 0) {
                    b = num;
                    cnt2 = 1;
                } else {
                    --cnt1;
                    --cnt2;
                }
            }
            cnt1 = cnt2 = 0;
            for (int num : nums) {
                if (num == a) {
                    ++cnt1; 
                } else if (num == b) {
                    ++cnt2; 
                }
            }

            if (cnt1 > n / 3) {
                res.push_back(a); 
            }

            if (cnt2 > n / 3) {
                res.push_back(b); 
            }

            return res;
        }
};
Last update: April 1, 2022