C++ O(n) solution.


  • -1
    C
    vector<int> majorityElement(vector<int>& nums) {
        int cand1, cand2, count1, count2;
        cand1 = cand2 = count1 = count2 = 0;
        for (auto& num: nums) {
            if (count1 == 0) {
                cand1 = num;
            } else if (count2 == 0) {
                cand2 = num;
            } 
            if (cand1 == num) {
                count1++;
            } else if (cand2 == num) {
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        vector<int> res;
        if (count(nums.begin(), nums.end(), cand1) > nums.size()/3)
            res.push_back(cand1);
        if (count(nums.begin(), nums.end(), cand2) > nums.size()/3 && cand1 != cand2)
            res.push_back(cand2);
        return res;
    }
    
    vector<int> majorityElement1(vector<int>& nums) {
        map<int, int> myMap;
        for (auto& num: nums) 
            myMap[num]++;
        vector<int> res;
        for (auto it = myMap.begin(); it != myMap.end(); it++) 
            if (it->second > nums.size()/3)
                res.push_back((*it).first);
        return res;
    }

  • 0
    Z

    wrong answer for the method vector<int> majorityElement(vector<int>& nums)


  • 0
    E

    You don't fit to memory and time limits...

    Memory:

    You are using additional 2 * sizeof(int) * sizeof(char) * n* by using std::map<int, int>. Also your solution does not in

    Running time

    You are inserting and iterating over you map, so insert will take nlog(n) + n


Log in to reply
 

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