class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> result;
if (nums.size() == 0) return result;
if (nums.size() == 1) {
result.push_back(nums[0]);
return result;
}
int c1 = 0, c2 = 0;
int m1 = nums[0], m2 = 0;
for(int i = 0; i < nums.size(); i++) {
int tar = nums[i];
if (tar == m1) ++c1;
else if (tar == m2) ++c2;
else if (c1 == 0) {
m1 = tar;
c1 = 1;
} else if (c2 == 0) {
m2 = tar;
c2 = 1;
} else {
--c1;
--c2;
}
}
c1 = 0, c2 = 0;
for(int i = 0; i < nums.size(); i++) {
if (m1 == nums[i]) ++c1;
else if (m2 == nums[i]) ++c2;
}
if (c1 > nums.size()/3) result.push_back(m1);
if (c2 > nums.size()/3) result.push_back(m2);
return result;
}
};