Not the best AC solution, but it just provides some ideas by using lower_bound


  • 0
    K

    I have seen similar question in google interview. Find the numbers appear more than [n/4]times in a sorted array.

    class Solution {
    public:
    vector<int> majorityElement(vector<int>& nums) {
        if(nums.size()==1)return nums;
        if(nums.size()==0)return {};
        sort(nums.begin(), nums.end());
        vector<int>res;
        
        int size=nums.size();
        
        int a=nums[size/3], b=nums[2*size/3];
        
        int countA=upper_bound(nums.begin(), nums.end(), a) - lower_bound(nums.begin(), nums.end(), a);
        int countB=upper_bound(nums.begin(), nums.end(), b) - lower_bound(nums.begin(), nums.end(), b);
        
        if(countA > size/3)res.push_back(a);
        if(a!=b && countB > size/3)res.push_back(b);
        
        return res;
    }
    };

Log in to reply
 

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