Leetcode 275 Solution

https://leetcode.com/problems/h-index-ii

Thinking Process

Let’s first figure out a linear solution, which is straightforward. We’ll just go through the `citations` array, and try each element `i`. if `citations[i] >= n - i`, we know that this scientist’s index is at least `n - i`. So let’s just do that for each element, and the first one that meets the condition `citations[i] >= n - i` is our target, and the result will be `n - i`.

Now, let’s try to make it `O(lg N)`. Remember our binary search principle here. In this question, the function `citations[i] >= n - i` has already helped us map the original array to an `0-1` array, and our goal is to find the index of the first `1`. We’ll just need to put it into our binary search template `binary_search_template`, and we get the result.

Time & Space Complexity

Assuming `N` is the size of the array:

• Time complexity: `O(lg N)`
• Space complexity: `O(1)`

Solution

``````class Solution {
public:
int hIndex(vector<int>& citations) {
int l = 0;
int r = citations.size() - 1;

while (l <= r)
{
int m = (l + r) / 2;

if (citations[m] >= citations.size() - m)
r = m - 1;
else
l = m + 1;
}

return citations.size() - l;
}
};
``````