Given an integer array of size n, find all elements that appear more than ⌊n/3⌋ ⌊ n / 3 ⌋ times. The algorithm should run in linear time and in O(1) space.
The algorithm we applied in this problem named Boyer-Moore Majority Vote algorithm.
There is a tricky point in this solution, that is the num_1 and num_2 cannot guarantee be the number we want. Therefore, we need to check if num_1 and num_2 appear more than ⌊n/3⌋ ⌊ n / 3 ⌋ times in the whole array (from line 34 to line 41). On the other hand, what this algorithm can guarantee is that if a number appears more than ⌊n/3⌋ ⌊ n / 3 ⌋ times, then it must be in the num_1 or num_2 .
这道题目采用的是Boyer-Moore Majority Vote算法，其中主要的一个问题是num_1和num_2里面保存的究竟是什么？简单点说，如果一个数在数组中出现的次数超过了 ⌊n/3⌋ ⌊ n / 3 ⌋ 次，那么它一定会被保存到num_1或num_2中。但是反过来，就不成立了，num_1或num_2中的数不一定出现的次数不一定超过了 ⌊n/3⌋ ⌊ n / 3 ⌋ 次。这就是为什么需要检查num_1和num_2在数组中出现的次数。
class Solution { public: vector<int> majorityElement(vector<int>& nums) { vector<int> ret; int cnt_1 = 0, cnt_2 = 0; int num_1 = -1, num_2 = -1; int size = nums.size(); for(int i = 0; i < size; i++) { if(num_1 == nums[i]) cnt_1++; else if(num_2 == nums[i]) cnt_2++; else if(cnt_1 == 0) { cnt_1++; num_1 = nums[i]; } else if(cnt_2 == 0) { cnt_2++; num_2 = nums[i]; } else { cnt_1--; cnt_2--; } } cnt_1 = cnt_2 = 0; for(int i = 0; i < size; i++) { if(nums[i] == num_1) cnt_1++; else if(nums[i] == num_2) cnt_2++; } if(cnt_1 > size / 3) ret.push_back(num_1); if(cnt_2 > size / 3) ret.push_back(num_2); return ret; } };