275. H-Index II #

Problem #

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.”

Example:

Input: citations = [0,1,3,5,6]
Output: 3 
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had 
             received 0, 1, 3, 5, 6 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note:

If there are several possible values for h, the maximum one is taken as the h-index.

Follow up:

• This is a follow up problem to  H-Index, where citations is now guaranteed to be sorted in ascending order.
• Could you solve it in logarithmic time complexity?

Problem Summary #

Given an array of citations for a researcher’s papers (citation counts are non-negative integers), where the array is sorted in ascending order. Write a method to compute the researcher’s h-index.

Definition of h-index: “h stands for “high citations”; a researcher’s h-index means that among his/her N papers, at most h papers have each been cited at least h times. (Each of the remaining N - h papers has no more than h citations.)”

Note:

• If there are multiple possible values for h, the h-index is the largest one.

Follow-up:

• This is an extension of H-Index. In this problem, the citations array is guaranteed to be sorted. Can you optimize your algorithm to logarithmic time complexity?

Solution Approach #

• Given an array representing the number of citations for each of the author’s papers, we are required to find the author’s h-index. Definition of h-index: “high citations” (high citations), a researcher’s h-index means that among his/her N papers, at most h papers have each been cited at least h times. (Each of the remaining N - h papers has no more than h citations.)
• In this problem, we need to find the h-index, which means finding a boundary where the maximum h-index is located. Binary search can be used to solve this problem. When len(citations)-mid > citations[mid], it means the boundary of the h-index must be on the right, because at most len(citations)-mid papers have citation counts greater than citations[mid]. Otherwise, the boundary of the h-index is on the left; shrink the boundary and continue binary search. After finding the boundary, the final value to compute is the h-index, and len(citations) - low is the result.

Code #

package leetcode

func hIndex275(citations []int) int {
	low, high := 0, len(citations)-1
	for low <= high {
		mid := low + (high-low)>>1
		if len(citations)-mid > citations[mid] {
			low = mid + 1
		} else {
			high = mid - 1
		}
	}
	return len(citations) - low
}