An nlogn solution with binary search


  • 0
    G
    class Solution {
    public:
        int hIndex(vector<int>& citations) 
        {
            sort(citations.begin(),citations.end());
            
            int start = 0;
            int end = citations.size();
            
            while(start < end)
            {
                int med = (start + end)/2;
                
                if(citations.size() - med <= citations[med])
                {
                    if(med == 0 || citations.size() - med + 1 > citations[med - 1])
                    {
                        return (min((int)citations.size() - med,citations[med]));
                    }
                    
                    end = med;
                }
                
                if(citations.size() - med > citations[med])
                {
                    start = med + 1;
                }
            }
            
            return (0);
        }
    };

Log in to reply
 

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