# 229. Majority Element II

• Time: $O(n)$
• Space: $O(1)$
  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 30 31 32 33 34 35 class Solution { public: vector majorityElement(vector& nums) { vector ans; int candidate1 = 0; int candidate2 = 1; // Any number different from candidate1 int countSoFar1 = 0; // # of candidate1 so far int countSoFar2 = 0; // # of candidate2 so far for (const int num : nums) if (num == candidate1) { ++countSoFar1; } else if (num == candidate2) { ++countSoFar2; } else if (countSoFar1 == 0) { // Assign new candidate candidate1 = num; ++countSoFar1; } else if (countSoFar2 == 0) { // Assign new candidate candidate2 = num; ++countSoFar2; } else { // Meet a new number, so pair out previous counts --countSoFar1; --countSoFar2; } const int count1 = count(nums.begin(), nums.end(), candidate1); const int count2 = count(nums.begin(), nums.end(), candidate2); if (count1 > nums.size() / 3) ans.push_back(candidate1); if (count2 > nums.size() / 3) ans.push_back(candidate2); return ans; } }; 
  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 30 31 32 33 34 35 36 37 38 39 40 class Solution { public List majorityElement(int[] nums) { List ans = new ArrayList<>(); int candidate1 = 0; int candidate2 = 1; // Any number different from candidate1 int countSoFar1 = 0; // # of candidate1 so far int countSoFar2 = 0; // # of candidate2 so far for (final int num : nums) if (num == candidate1) { ++countSoFar1; } else if (num == candidate2) { ++countSoFar2; } else if (countSoFar1 == 0) { // Assign new candidate candidate1 = num; ++countSoFar1; } else if (countSoFar2 == 0) { // Assign new candidate candidate2 = num; ++countSoFar2; } else { // Meet a new number, so pair out previous counts --countSoFar1; --countSoFar2; } int count1 = 0; int count2 = 0; for (final int num : nums) if (num == candidate1) ++count1; else if (num == candidate2) ++count2; if (count1 > nums.length / 3) ans.add(candidate1); if (count2 > nums.length / 3) ans.add(candidate2); return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution: def majorityElement(self, nums: List[int]) -> List[int]: ans1 = 0 ans2 = 1 count1 = 0 count2 = 0 for num in nums: if num == ans1: count1 += 1 elif num == ans2: count2 += 1 elif count1 == 0: ans1 = num count1 = 1 elif count2 == 0: ans2 = num count2 = 1 else: count1 -= 1 count2 -= 1 return [ans for ans in (ans1, ans2) if nums.count(ans) > len(nums) // 3]