Majority Element II - Medium - L
Published:
Question
- https://leetcode.com/problems/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?
Approach
- Bayer Moore’s Majority Algorithm.
Solution
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n = nums.size();
vector<int> ans;
if(n==0) {
return ans;
}
if (n==1) {
ans.push_back(nums[0]);
return ans;
}
int l1 = nums[0];
int l2 = 0;
int l1c = 0;
int l2c = 0;
for(int i=0; i<n; i++) {
if(nums[i]==l1) {
l1c++;
} else if (nums[i]==l2) {
l2c++;
} else if (l1c==0) {
l1 = nums[i];
l1c = 1;
} else if (l2c==0) {
l2 = nums[i];
l2c = 1;
} else {
l1c--;
l2c--;
}
}
l1c=0;
l2c=0;
for(int i=0;i<n;i++) {
if(nums[i]==l1) {
l1c++;
}
if(nums[i]==l2) {
l2c++;
}
}
if(l1c>n/3) {
ans.push_back(l1);
}
if(l2c>n/3 && l1!=l2) {
ans.push_back(l2);
}
return ans;
}
};