[LeetCode] Majority Element II
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.
解题思路：
此前做了一道题目，返回主要元素，其中主要元素的定义是出现次数大于n/2的元素。当初投票法非常不错。类似的，这道题也可以用投票法，但是稍微复杂一下。注意到，对于一个数组来说，大于n/3的元素最多有2个。于是可以用两个变量来记录出现的候选主要元素。
设候选主要元素为can1，can2，其票数分别是count1，count2（初始化均为0）。逐个扫描nums内的元素nums[i]，分情况讨论。
1、假设还未统计任何数，即count1=0&&count2=0，则can1=nums[i]，count1=1
2、can1和can2其中一个没有初始化（设can2，即count2=0），且nums[i]!=can1，那么can2=nums[i]，count2=1。对称另一种情况容易知道。
3、假设can1和can2两个都初始化了（count1!=0并且count2!=0），但是can1!=nums[i]并且can2!=nums[i]。那么count1和count2均减1
4、若count1!=0并且can1==nums[i]，那么count1++。同样，若count2!=0并且can2==nums[i]，那么count2++。
最后，验证can1和can2的出现次数即可。
下面是代码：
class Solution {
public:
vector majorityElement(vector& nums) {
vector result;
int len = nums.size();
int can1=0, count1 = 0, can2 = 0, count2 = 0;
for(int i=0; ilen/3){
result.push_back(can1);
}
}
if(count2!=0){
count2 = 0;
for(int i=0; ilen/3){
result.push_back(can2);
}
}
return result;
}
};
原文作者：；如有侵权，请联系管理员删除。
