229. Majority Element II | LeetCode Solution

 229. Majority Element II

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

 

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

 

Follow up: Could you solve the problem in linear time and in O(1) space?

The solution to the above question is 

class Solution {

public:

    vector<int> majorityElement(vector<int>& nums) {

        int n=floor(nums.size()/3);

        vector<int>ans;

        int num1=-1;

        int num2=-1;

        int cnt1=0;

        int cnt2=0;

        for(int i=0; i<nums.size(); i++){

            if(nums[i]==num1)cnt1++;

            else if(nums[i]==num2)cnt2++;

            else if(cnt1==0){num1=nums[i];cnt1=1;}

            else if(cnt2==0){num2=nums[i];cnt2=1;}

            else{

                cnt1--;

                cnt2--;

            }

        }

        int c1=0,c2=0;

        for(int i=0; i<nums.size(); i++){

            if(nums[i]==num1)c1++;

            if(nums[i]==num2)c2++;

        }

        if(c1>n)ans.push_back(num1);

        if(c2>n && num1!=num2)ans.push_back(num2);

        return ans;

    }

};