C++ 24ms, O(n) time, O(1) space


  • 2

    The size of vector res, val, count can at most be size of 2. So it is constant space.

    class Solution {
    public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int>res;
        if (nums.empty()) return res;
        vector<int> val,count;
        for (int i=0;i<nums.size();i++){
            if (val.empty()){
                val.push_back(nums[i]);
                count.push_back(1);
            }else if (val.size()==1){
                if (val[0]==nums[i]){
                    count[0]++;
                }else{  
                    val.push_back(nums[i]);
                    count.push_back(1);
                }
            }else {    // size == 2
                if (val[0]==nums[i]){
                    count[0]++;
                }else if (val[1]==nums[i]){
                    count[1]++;
                }else{
                    count[0]--;
                    count[1]--;
                    if (count[1]==0){val.pop_back();count.pop_back();}
                    if (count[0]==0){val.erase(val.begin());count.erase(count.begin());}
                }
            }
        }
        for (int i=0;i<val.size();i++){
            int temp=0;
            for (int j=0;j<nums.size();j++){
                if (nums[j]==val[i]) temp++;
            }
            if (temp>nums.size()/3) res.push_back(val[i]);
        }
        return res;
    }
    };

  • 0

    your answer is O(n)space


  • 0

    it is O(1). The size of vector val and count can only be 0 or 1 or 2 at any time. They are constant space.


  • 0
    H

    Does it work with, for example, [1,1,1,1,2,3,4,5,6,7,8] ?


Log in to reply
 

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