Problem description:

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

1
2
3
4
Example 1:

Input: [3,2,3]
Output: [3]
1
2
3
4
Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Solution:
The essential concepts is you keep a counter for the majority number X. If you find a number Y that is not X, the current counter should deduce 1. The reason is that if there is 5 X and 4 Y, there would be one (5-4) more X than Y. This could be explained as “4 X being paired out by 4 Y”.

And since the requirement is finding the majority for more than ceiling of [n/3], the answer would be less than or equal to two numbers.
So we can modify the algorithm to maintain two counters for two majorities.

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
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int num0 = 0, num1 = 1, count0 = 0, count1 = 0;
        
        for (auto x: nums) {
            //find two majority element
          if (x == num0) count0++;
          else if (x == num1) count1++;
          else if (! count0) num0 = x, count0 = 1;
          else if (! count1) num1 = x, count1 = 1;
          else count0--, count1--;
        }
        
        //set to zero is because only need to count these two element
        count0 = count1 = 0;
        
        for (auto x: nums)
          if (x == num0) count0++;
          else if (x == num1) count1++;
        vector<int> res;
        if (count0 > nums.size()/3) res.push_back(num0);
        if (count1 > nums.size()/3) res.push_back(num1);
        return res;
        
    }
};

reference:
https://gregable.com/2013/10/majority-vote-algorithm-find-majority.html