binary search


  • 0
    Y
    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            long N = citations.size();
            if(N == 0)
                return 0;
            sort(citations.begin(),citations.end(),greater<int>());
            long s = 0, e = N - 1;
            while(s < e - 1){
                long m = (s + e) / 2;
                // cout << m << endl;
                if(citations[m] < m + 1)
                    e = m - 1;
                else if(citations[m + 1] > m + 1)
                    s = m + 1;
                else 
                    s = m;
            }
            if(citations[e] >= e + 1 && (e >= N-1 || citations[e+1] <= e + 1))
                return e+1;
            else if(citations[s] >= s + 1 && (s >= N-1 || citations[s + 1] <= s + 1))
                return s+1;
            else if(citations[N-1] >= N && citations[N] <= N)
                return N+1;
            else
                return 0;
        }
    };
    

Log in to reply
 

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