C++ O(log n) solution by binary search WITH explanation


  • 0
    U

    Simply find the maximum k that satisfies citations[n-1-k] > k by binary search.
    Return k+1 as the answer.

    class Solution {
    public:
        bool valid(vector<int>& citations, int n, int k) {
            if (k < n)
                return (citations[n-1-k] > k);
            else
                return false;
        }
        
        int hIndex(vector<int>& citations) {
            int n = citations.size();
            if (!n) return 0;
            int st = 0;
            int ed = n - 1;
            if (!valid(citations, n, st)) return 0;
            if (valid(citations, n, ed)) return n;
            while (ed - st > 1) {
                int mid = (st+ed)/2;
                if (valid(citations, n, mid))
                    st = mid;
                else
                    ed = mid;
            }
            return st+1;
        }
    };
    

Log in to reply
 

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