My O(n) time solution ,20ms


  • 33
    L

    My idea comes from Majority Vote algroithm,http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html.Now we vote two numbers simultaneously. if the next number is differents from them both.then the two numbers' votes minus one. If some number's vote comes zero,then vote the next number.Every time vote minus,it is the same that we remove the three numbers from the array.And the majority elemnts of original still are the majority elements in the end. So check t1 and t2 are the majority elements of original array at last.

    vector<int> majorityElement(vector<int>& nums) {
            int t1,t2,n1=0,n2=0;  //numbers t1 and t2,votes' numbers n1,and n2.
            for(int i=0;i<nums.size();++i)
            {
                if(n1!=0&&t1==nums[i]){++n1;continue;} 
                if(n2!=0&&t2==nums[i]){++n2;continue;}
                if(n1==0){ t1=nums[i];++n1;continue;}
                if(n2==0){ t2=nums[i];++n2;continue;}
                --n1;--n2;
            }
            int z1=0,z2=0;
            for(int i=0;i<nums.size();++i)
            {
                if(n1>0){ if(nums[i]==t1) ++z1;}
                if(n2>0) {if(nums[i]==t2) ++z2;}
            }
            vector<int> ret;
             //check t1 and t2.
            if(z1>nums.size()/3) ret.push_back(t1);
            if(z2>nums.size()/3) ret.push_back(t2);
            return ret;
        }
    

  • 0
    J

    Is this still applicable for [n / 4] ?


  • 0
    L

    I donot think so, if the case is [n/4], it should keep three numbers instead of 2. the space complexity should be O(m) where m is the division-1.


Log in to reply
 

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