LeetCode [229] Majority Element II

 229. Majority Element II

Medium

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?

 

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { public: vector<int> majorityElement(vector<int>& nums) { vector<int> ret; int n1, c1 = 0, n2, c2 = 0; for(auto n:nums){ if(c1>0 && n==n1){ c1++; }else if(c2>0 && n==n2){ c2++; }else if(c1==0){ c1++; n1 = n; }else if(c2==0){ c2++; n2 = n; }else{ c1--; c2--; } } int t1 = 0, t2 = 0, n = nums.size(); for(auto n:nums){ if(c1>0 && n==n1) t1++; if(c2>0 && n==n2) t2++; } if(t1>n/3) ret.push_back(n1); if(t2>n/3) ret.push_back(n2); return ret; } };