C++, 3 lines O(n) / 8 lines binary search O(logn)


  • 0
    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            int i = 0, j = citations.size() - 1;
            while(j >= 0 && citations[j] > i) i++, j--;
            return i;
        }
    };
    

    Binary Search

    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            int lo = 0, len = citations.size(), hi = len - 1;
            int mid = lo + (hi - lo) / 2;
            while(lo <= hi){
                if(citations[mid] >= len - mid) hi = mid - 1;
                else lo = mid + 1;
                mid = lo + (hi - lo) / 2;
            }
            return len - lo;
        }
    };
    

Log in to reply
 

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