记住格式：
Majority Element I：
candidate = nums[0], cnt = 1, 相同加，不同减。
class Solution {
public:
int majorityElement(vector<int>& nums) {
if(nums.empty()) return 0;
int candidate = nums[0];
int cnt = 1;
for(int i=1; i<nums.size(); i++){
if(nums[i] == candidate) cnt++;
else{
cnt--;
if(cnt == 0){
candidate = nums[i];
cnt = 1;
}
}
}
return candidate;
}
};
Majority Element II：
candidate1 = candidate2 = nums[0]
cnt1 = 1, cnt2 = 0;
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
if(nums.empty()) return vector<int>();
int candidate1 = nums[0], candidate2 = nums[0];
int cnt1 = 1, cnt2 = 0;
for(int i=1; i<nums.size(); i++){
if(cnt1 > 0 && nums[i] == candidate1){
cnt1++;
}else if(cnt2 > 0 && nums[i] == candidate2){
cnt2++;
}else if(cnt1 == 0){
candidate1 = nums[i];
cnt1 = 1;
}else if(cnt2 == 0){
candidate2 = nums[i];
cnt2 = 1;
}else{
cnt1--; cnt2--;
}
}
vector<int> ret;
cnt1 = 0; cnt2 = 0;
for(int i=0; i<nums.size(); i++){
if(nums[i] == candidate1) cnt1++;
else if(nums[i] == candidate2) cnt2++;
}
if(cnt1 > nums.size()/3) ret.push_back(candidate1);
if(cnt2 > nums.size()/3) ret.push_back(candidate2);
return ret;
}
};
