Hashmap solution

• I think it should be more clear if we use a hash map of size 2 to solve the problem.

`````` class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
unordered_map<int, int> cand;
for(int i = 0; i < nums.size(); i++) {
cand[nums[i]]++;
if(cand.size() > 2) {
auto it = cand.begin();
while(it != cand.end()) {
it->second--;
if(it->second == 0)
it = cand.erase(it);
else
it++;
}
}
}
int n1 = 0;
int n2 = 0;
vector<int> can;
for(auto it:cand){
can.push_back(it.first);
}
for(int i = 0; i < nums.size(); i++) {
if(can.size()>0 && nums[i] == can[0])
n1++;
if(can.size()>1 && nums[i] == can[1])
n2++;
}
vector<int> res;
int n = nums.size();
if(n1 * 3 > n)
res.push_back(can[0]);
if(n2 * 3 > n)
res.push_back(can[1]);
return res;
}
};``````

• Is this O(1) space cost?

• It should be.
Since the size of hash map can not be greater than 2, it can be considered constant space.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.