cpp in-space O(n) solution


  • 1
    P
    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            vector<int> ans;
            if(nums.empty()) return ans;
            nth_element(nums.begin(), nums.begin() + nums.size() / 3, nums.end());
            int a = nums[nums.size()/3],count = 0;
            for(auto m:nums) if(a==m) count++;
            if(count>nums.size()/3) ans.push_back(a);
            nth_element(nums.begin(), nums.begin() + nums.size()-nums.size()/3-1, nums.end());
            int b = nums[nums.size()-nums.size()/3-1];
            if(b==a) return ans;
            count = 0;
            for(auto m:nums) if(b==m) count++;
            if(count>nums.size()/3) ans.push_back(b);
            return ans;
        }
    };
    

    check the n/3th and 2n/3th elements.


  • 0
    B

    Good idea to use nth_element~


Log in to reply
 

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