[LeetCode] Majority Element II

Well, this problem becomes a little trickier since there may be more than one majority element. But, there can be at most two of them. This can be proved using proof by contradiction. If there are not less than 3 majority element and each appears more than n / 3 times, then nums will have 3 * n / 3 > n elements, which is a contradiction. Note that the floor sign does not affect the correctness of this proof. You may try some examples and convince yourself of this.

Now we maintain a vector<int> major for the majority elements. Once we meet an element which has appeared more than n / 3 times and have not been added to major, we add it tomajor. For counting the number of appearances, we use an unordered_map<int, int> counts. For telling whether it has been added, we use an unordered_set<int> exist to store the added elements.

Since we visit each element exactly once and the operations (search, insertion) w.r.t counts andexist (both are hash tables) is O(1), this idea can simply be proved to be of O(n) time-complexity.

The code is as follows.

 1 class Solution {
 2 public:
 3     vector<int> majorityElement(vector<int>& nums) {
 4         vector<int> major; 
 5         unordered_map<int, int> counts;
 6         unordered_set<int> exist;
 7         int n = nums.size();
 8         for (int i = 0; i < n; i++) {
 9             counts[nums[i]]++;
10             if (counts[nums[i]] > n / 3 && exist.find(nums[i]) == exist.end()) {
11                 major.push_back(nums[i]);
12                 exist.insert(nums[i]);
13             }
14             if (major.size() == 2) break;
15         }
16         return major;
17     }
18 };

Due to the use of counts, the above code is not of O(1) space. If you want to have an O(1)-space solution, you need to adapt the idea of Boyer-Moore Voting here. This link has a nice explanation.

 1 class Solution {
 2 public:
 3     vector<int> majorityElement(vector<int>& nums) {
 4         int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;
 5         for (int num : nums) {
 6             if (num == candidate1) count1++;
 7             else if (num == candidate2) count2++;
 8             else {
 9                 if (!count1) {
10                     candidate1 = num;
11                     count1++;
12                 }
13                 else if (!count2) {
14                     candidate2 = num;
15                     count2++;
16                 }
17                 else {
18                     count1--;
19                     count2--;
20                 }
21             }
22         }
23         count1 = count2 = 0;
24         for (int num : nums) {
25             if (num == candidate1) count1++;
26             else if (num == candidate2) count2++;
27         }
28         int n = nums.size();
29         vector<int> majority;
30         if (count1 > n / 3) majority.push_back(candidate1);
31         if (count2 > n / 3) majority.push_back(candidate2);
32         return majority;
33     }
34 };