229. Majority Element II

For this problem, we need to extend Boyer-Moore Majority Vote algorithm a little bit. Instead of keeping one number, we need to keep two numbers. If first time to see a number (i.e. either count for number 1 or count for number 2 is 0), we save that number. If we see the saved number again, count one more. If we a new number isn't seen before, we reduce the count for both saved numbers (i.e. cancel one appearance for each). Eventually, we'll have two majority numbers. Then we check if these two majority numbers appear more than third n times. Therefore, the total running time is O(2n).

1:  class Solution {  
2:  public:  
3:    vector<int> majorityElement(vector<int>& nums) {  
4:      int n1 = 0, n2 = 0, c1 = 0, c2 = 0;  
5:      vector<int> res;  
6:      for (int n : nums) {  
7:        if (n == n1) c1++;  
8:        else if (n == n2) c2++;  
9:        else if (!c1) { n1 = n; c1++; }  
10:        else if (!c2) { n2 = n; c2++; }  
11:        else { c1--; c2--;}  
12:      }  
13:      c1 = 0; c2 = 0;  
14:      for (int n : nums) {  
15:        if (n == n1) c1++;  
16:        else if (n == n2) c2++;  
17:      }  
18:      if (c1 > nums.size() / 3) res.push_back(n1);  
19:      if (c2 > nums.size() / 3) res.push_back(n2);  
20:      return res;  
21:    }  
22:  };