# 229. Majority Element II

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

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

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

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

# Solution

Approach 1: Boyer-Moore Voting Algorithm adapted to the n/3 case.

# Code (Python)

Approach 1:

# Code (C++)

Approach 1:

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> res;
        if (nums.size() == 0)
            return res;
        int num1 = 0;
        int num2 = 0;
        int size1 = 0;
        int size2 = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (size1 > 0 && num1 == nums[i])
            {
                size1++;
            }
            else if (size2 > 0 && num2 == nums[i])
            {
                size2++;
            }
            else if (size1 == 0)
            {
                num1 = nums[i];
                size1++;
            }
            else if (size2 == 0)
            {
                num2 = nums[i];
                size2++;
            }
            else
            {
                size1--;
                size2--;
            }
        }
        int count1 = 0;
        int count2 = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i] == num1)
                count1++;
            else if (nums[i] == num2)
                count2++;
        }
        if (count1 > nums.size() / 3)
            res.push_back(num1);
        if (count2 > nums.size() / 3)
            res.push_back(num2);
        return res;
    }
};