H-Index

Question

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

For example, given citations = [3, 0, 6, 1, 5], which 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, his h-index is 3.

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

Tags

• Sort
• Hash Table

Thought

There are two different approaches to solve this problem: sort, hash table.

For sorting approach, the citation list will be sorted with reversed order and compare the index and the value for each item in the sorted list.

For hash table, a new array with N+1 items need to be initialized to store the number of papers with different citations.

Here, the solution for sorting approach is provided.

Code

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        citation_list = list(citations)
        citation_list.sort()
        citation_list.reverse()
        citation = 0
        for count, citation in enumerate(citation_list):
            if count >= citation:
                return count
        return len(citations)