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