H-Index II

LeetCode Q 275 - H-Index II

Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

Similar question: H-Index

Solution

The idea is to search for the first index from the sorted array so that :
citations[index] >= length(citations) - index. And return (length - index) as the result.

Since the given citations array is already sorted, so the time complexity is O(logN).

Code:

public int hIndex(int[] citations) {
	if (citations == null || citations.length == 0) return 0;
	int left = 0, right = citations.length - 1, len = citations.length;
	while (left <= right) {  //  (left < right) --> [0, 0] won't pass 
		int mid = left + (right - left) / 2;
		if (citations[mid] == len - mid)
			return len - mid;
		else if (citations[mid] < len - mid)
			right = mid - 1;
		else
			left = mid + 1;
	}
	return len - left;
}