Solving this question using a map that stores the frequency of each element is pretty straightforward. This problem is an extension of LC 169. Majority Element and I highly recommend you to view the solution of that and try to solve this problem on your own. It is an extension of the famous Boyre Moore’s Majority Voting Element algorithm. The solution below is pretty straightforward to understand once you know the actual algorithm (applied in LC 169).
Instead of going through the array twice, here we have to go through the array three times. The first time we keep track of the potential majority elements using the variables num1, count1, num2, count2. The second time we check whether num1 is actually a majority element and the third time we check the same for num2. Note that there cannot be more than two majority elements as each has to appear strictly more than floor(n/3) times.
vector<int> majorityElement(vector<int>& nums) {
int size = nums.size(), num1=-1, count1=0, num2=-1, count2=0;
vector<int> ans;
for (int i=0; i<size; i++) {
if (nums[i] == num1) {
count1++;
continue;
}
if (nums[i] == num2) {
count2++;
continue;
}
if (count1 == 0) {
num1 = nums[i];
count1++;
continue;
}
if (count2 == 0) {
num2 = nums[i];
count2++;
continue;
}
count1--;
count2--;
}
count1=count2=0;
for (int i=0; i<size; i++) {
if (nums[i] == num1)
count1++;
if (nums[i] == num2)
count2++;
}
if (count1>size/3)
ans.push_back(num1);
if (count2>size/3)
ans.push_back(num2);
return ans;
}
Time complexity: O(n)
Space complexity: O(1)