274. H-Index

Problem Statement

link: LeetCode.cn LeetCode

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher’s h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

Example:

Input: citations = [3,0,6,1,5] Output: 3

Input: citations = [1,3,1] Output: 1

Solution Approach

The solution employs counting sort to efficiently process citation counts, using an array to track the number of papers with specific citation values, and iteratively determines the researcher’s h-index by finding the maximum value of h where the researcher has published at least h papers, each cited at least h times.

Algorithm

1. Counting Sort: Utilize counting sort to process the citation counts efficiently, allocating an array to store the count of papers with specific citation values.
2. Updating Counts: Iterate through the given citation array, updating the count array with the occurrence of each citation value at the corresponding index, considering the minimum of the citation value and the total number of papers.
3. Determining H-Index: Start from the end of the count array, iteratively decrement the potential h-index (h) while accumulating the sum of counts (s). Stop when s becomes greater than or equal to h, and return the final value of h as the researcher’s h-index.

Implement

    class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        paper = [0] * (n + 1)
        for c in citations:
            paper[min(n, c)] += 1
        s, h = paper[-1], n
        while s < h:
            h -= 1
            s += paper[h]
        return h
    
       

    
    

Twitter  facebook  Email