一名科研人員的 h 指數(shù)是指 ta 的 (n 篇論文中) 總共有 h 篇論文分別被引用了至少 h 次。且其余的 n - h 篇論文每篇被引用次數(shù)不超過 h 次。

如果 n 篇論文已經(jīng)排序好，那么使用二分法能達(dá)到 的時(shí)間復(fù)雜度。

def hIndex(self, citations: List[int]) -> int:
    n = len(citations)
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if citations[mid] < n - mid:
            lo = mid + 1
        else:
            hi = mid
    return n - lo

使用線性掃描的時(shí)間復(fù)雜度是

def hIndex(self, citations: List[int]) -> int:
    citations.sort(reverse=True)
    res = 0
    for i in range(len(citations)):
        if citations[i] >= i + 1:
            res = max(res, i + 1)
    return res

如果未排序，排序后再二分的復(fù)雜度是 。

也可直接使用桶排序，發(fā)表 n 篇文章，h 指數(shù)最高能達(dá)到 n，因此維護(hù)一個(gè) n + 1 大小的桶再線性掃描即可。

def hIndex(self, citations: List[int]) -> int:
    n = len(citations)
    bucket = [0] * (n + 1)
    for i in citations:
        bucket[min(i, n)] += 1
    
    cnt = 0
    for i in reversed(range(n + 1)):
        cnt += bucket[i]
        if cnt >= i:
            return i
    return 0