The idea here is to select n/3-th element and 2n/3-th element as candidates. And then check if they appear more than n/3 times;

This solution does work, but the problem is I am not sure if it meets the O(1) space requirement.

```
vector<int> majorityElement(vector<int>& nums) {
int s=nums.size();
if(!s)
return {};
vector<int> res;
int count=0, candidate1=0, candidate2=0;
// reference here http://www.cplusplus.com/reference/algorithm/nth_element/
nth_element(nums.begin(), nums.begin() + s / 3, nums.end());
candidate1=nums[s/3]
for(auto num:nums)
num==candidate1 ? count++ : count;
if(count>s/3)
res.push_back(candidate1);
nth_element(nums.begin(), nums.begin() + 2 * s / 3, nums.end());
count=0, candidate2=nums[2*s/3];
for(auto num:nums)
num==candidate2 ? count++ : count;
if(count>s/3 && candidate1 != candidate2)
res.push_back(candidate2);
return res;
}
```