9-liner O(N) time O(1) space


  • 0
        vector<int> majorityElement(vector<int>& nums) 
        {
            int cnt[2] = {0, 0}, val[2] = {0, 1};
            for (int x : nums)
                if (x == val[0] || x == val[1]) cnt[x==val[1]]++;
                else if (cnt[0]*cnt[1]) cnt[0]--, cnt[1]--;
                else val[(bool)cnt[0]] = x, cnt[(bool)cnt[0]]++;
            
            vector<int> res;
            for (int v : val)
              if (count(nums.begin(), nums.end(), v) > nums.size()/3) res.push_back(v);
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.