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

  • 0

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

    class Solution {
    vector<int> majorityElement(vector<int>& nums) {
        if(nums.size()==1)return nums;
        if(nums.size()==0)return {};
        sort(nums.begin(), nums.end());
        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.