LeetCode Q 274 - H-Index

Given an array of citations (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.”

Solution

Comparing with H-Index II, the given citations is unsorted. We can still use binary search to solve this question as we did in leetcodeQ275. Then the time complexity is O(NlogN). But we can optimize the solution using bucket sort (counting sort). The time complexity becomes O(N).

Assume n is the total number of papers, if we have n+1 buckets, number from 0 to n, then for any paper with reference corresponding to the index of the bucket, we increment the count for that bucket. The only exception is that for any paper with larger number of reference than n, we put in the n-th bucket.

Then we iterate from the back to the front of the buckets, whenever the total count exceeds the index of the bucket, meaning that we have the index number of papers that have reference greater than or equal to the index. Which will be our h-index result.

Some tricky cases: [5,5] -> 2 [0,0] -> 0

Code:

public int hIndex(int[] citations) {
	if (citations == null || citations.length == 0) return 0;
	int len = citations.length;
	int[] buckets = new int[len + 1];
	for (int citation: citations) {
		if (citation >= len) buckets[len]++;
		else buckets[citation]++;
	}

	int count = 0;
	for (int i = len; i >= 0; i--) {
		count += buckets[i];
		if (count >= i) return i;
	}

	return 0;
}

Reprint policy