[数据结构与算法]LeetCode 274/275 H指数（堆 heapq ，二分）

题目：

H 指数：一名科研人员的 N 篇论文中，总共有 h 篇论文分别被引用了至少 h 次。且其余的?N - h?篇论文每篇被引用次数?不超过 h 次。

H指数1：给定无序数列，求H指数。

H指数2：给定有序数列，在O(nlogn)求H指数。

题解：

H指数1：类似于堆排序，先建小顶堆 O(n)，每次取堆顶值O(nlogn)，判断是否满足h指数

H指数2：二分法，判断分到的值是否满足h指数O(nlogn)

源码：

H指数1：

import heapq
class Solution:
    def hIndex(self, citations: list[int]) -> int:
        n = len(citations)
        if n == 0:
            return 0
        heapq.heapify(citations)
        for h in range(n, 0, -1):
            if heapq.heappop(citations) >= h:
                return h
        return 0

H指数2：

class Solution:
    def hIndex(self, citations: list[int]) -> int:
        n = len(citations)
        if n == 0:
            return 0
        left = 0
        right = n - 1
        while left <= right:
            mid = left + (right - left) // 2
            h1 = n - mid
            if(citations[mid] >= h1):
                right = mid - 1
            else:
                left = mid + 1
        return n - (right + 1)