229.Majority Element II
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.
Hint:
How many majority elements could it possibly have?
这道题是Majority Element系列的第二题，要求O(n)的时间复杂度和O(1)的空间复杂度，题目中给出了暗示，要求先考虑一个序列中最多有多少个出现次数能超过1/3的元素，根据反证法，如果有三个符合要求的元素，那么数组的长度就不可能是n了，所以符合要求的元素最多有两个，但是最开始我并没能够从这个暗示里读出有价值的信息。
直到后来看了讨论区的答案才受到了启发，之前用过的majority voting algorithm是用来寻找出现次数过半的元素的，由于过半的元素只能有一个，所以只需要有一个count来统计投票就够了，这道题只不过是把可能符合条件的数变为2个，再加上一个count不就可以统计两个候选元素的得票状况了吗？其余步骤完全和之前相同。 代码如下：
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int curIndex1=0,curIndex2=0,count1=0,count2=0;
int size=nums.size(),i=0,tri=size/3;
vector<int>res;
for(i=0;i<nums.size();i++){
if(nums[i]==nums[curIndex1])
count1++;
else if(nums[i]==nums[curIndex2])
count2++;
else if(!count1){
count1=1;
curIndex1=i;
}
else if(!count2){
count2=1;
curIndex2=i;
}
else{
count1--;
count2--;
}
}
count1=0;
count2=0;
for(i=0;i<nums.size();i++){
if(nums[i]==nums[curIndex1])
count1++;
else if(nums[i]==nums[curIndex2])
count2++;
}
if(count1>tri)
res.push_back(nums[curIndex1]);
if(count2>tri)
res.push_back(nums[curIndex2]);
return res;
}
};