题目来源
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
要求求出数组中出现次数超过n/3的元素，原来想着直接哈希，但是需要O(1)空间，感觉有点熟悉，记得之前在宿舍说过类似的题目。线性时间并且O(1)空间！我猜应该用位操作？但是想不出来怎么操作。
看了答案，得用到一个经典算法，叫Boyer-Moore Majority Vote algorithm，多数投票算法，之前也学过的，算法也很简单，但是忘了…
就是设置一个候选人以及一个计数器，假如出现相同的就加1，不同的就减1，当减到0的时候就换一个候选人。
然后这道题就是稍微改一下，变成有两个候选人，其他的就都一样了，注意最后还要再判断一下两个候选人是否符合要求，因为可能一共就两个元素
代码如下：
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int n = nums.size();
vector<int> res;
int cad1 = 0, cad2 = 0, count1 = 0, count2 = 0;
for (int i=0; i<n; i++) {
if (nums[i] == cad1)
count1++;
else if (nums[i] == cad2)
count2++;
else {
if (count1 == 0) {
cad1 = nums[i];
count1++;
}
else if (count2 == 0) {
cad2 = nums[i];
count2++;
}
else {
count1--;
count2--;
}
}
}
count1 = 0, count2 = 0;
for (int i=0; i<n; i++) {
if (nums[i] == cad1)
count1++;
else if (nums[i] == cad2)
count2++;
}
if (count1 > n/3)
res.push_back(cad1);
if (count2 > n/3)
res.push_back(cad2);
return res;
}
};
