Hashmap solution


  • 0
    W

    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;
            }
        };

  • 0
    Z

    Is this O(1) space cost?


  • 0
    W

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


Log in to reply
 

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