Can anybody tell me if this C++ solution is O(1) space complexity?


  • 6
    B

    The idea here is to select n/3-th element and 2n/3-th element as candidates. And then check if they appear more than n/3 times;
    This solution does work, but the problem is I am not sure if it meets the O(1) space requirement.

        vector<int> majorityElement(vector<int>& nums) {
            int s=nums.size();
            if(!s)
                return {};
            vector<int> res;
            int count=0, candidate1=0, candidate2=0;
            
            // reference here http://www.cplusplus.com/reference/algorithm/nth_element/
            nth_element(nums.begin(), nums.begin() + s / 3, nums.end());  
            
            candidate1=nums[s/3]
            for(auto num:nums)
                num==candidate1 ? count++ : count;
            if(count>s/3)
                res.push_back(candidate1);
            
            nth_element(nums.begin(), nums.begin() + 2 * s / 3, nums.end());   
            
            count=0, candidate2=nums[2*s/3];
            for(auto num:nums)
                num==candidate2 ? count++ : count;
            if(count>s/3 && candidate1 != candidate2)
                res.push_back(candidate2);    
            
            return res;
        }

  • 0

    Yes, it definitely is. Very original solution. Thanks for sharing!


  • 1

    Function "nth_element" is quick select. It is an O(n) time and O(1) space algorithm.


  • 0
    J

    Very original!!!


Log in to reply
 

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