Problem description:

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

Example:

1
2
3
4
5
6
Input: citations = [3,0,6,1,5]
Output: 3 
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had 
             received 3, 0, 6, 1, 5 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.

Solution:

1
2
3
4
5
6
7
8
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort()
        n = len(citations)
        for i in range(n):
            if citations[i] >= (n-i):
                return n-i
        return 0

time complexity: $O(nlogn)$
space complexity: $O(1)$

Another thought is to use bucker sort. The idea is to see that the result can only range from 0 to the length of the array (because we can’t have h-index greater than the total papers published). So we create an array “arr” which acts like a HashMap (using pigeon hole principle) and loop backwards from the highest element, then we find total which is the total number of papers that has more than i citations, and we stop when total>=i (total number of papers with more than i citations >= i). We don’t need to keep going because we are trying the biggest i possible, we we stop and return the result.

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        bucket = [0]*(n+1)

        for cite in citations:
            if cite >= n:
                bucket[n] += 1
            else:
                bucket[cite] += 1
        total = 0
        for i in reversed(range(len(bucket))):
            total += bucket[i]
            if total >= i:
                return i

time complexity: $O(n)$
space complexity: $O(n)$

reference:
related problem: