229. Majority Element II | LeetCode Solution

 229Majority 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;
    }
};



Post a Comment

0 Comments