LeetCode Algorithm 274. H 指数

LeetCode Algorithm 274. H 指数

LeetCode Algorithm 274. H 指数是一道计算学术论文被引用次数与被引用次数的关系的题目。在这个问题中，我们需要计算一个学术论文集合中的 H 指数。

问题描述

给定一个整数数组 citations ，其中每个元素表示该研究的被引用次数，编写一个函数来计算 H 指数。

H 指数的定义为：“一个学者的 h 指数是指他（她）的 N 篇论文中至多有 h 篇论文分别被引用了至少 h 次，其余的 N - h 篇论文每篇被引用次数不多于 h 次。”

示例 1:

输入: citations = [3,0,6,1,5]

输出: 3 
解释: 给定数组表示研究者的论文数量和每篇论文的被引用次数。由于研究者有 5 篇论文每篇至少被引用了 3 次，其余的两篇每篇被引用次数不超过 3 次，所以它的 h 指数是 3。

说明:

如果存在多个可能的 h 指数，则最大的那个是定义中的 h 指数。

解题思路

要计算 H 指数，我们需要先将 citations 数组按照从大到小的顺序进行排序。排序后，我们可以遍历数组并根据定义计算 H 指数。

首先，我们定义一个变量 n 作为数组的长度。接着，我们使用两个指针 left 和 right 分别指向数组的起始和末尾。

我们通过一个循环来遍历数组，循环条件是 right - left + 1 >= citations[left]。在循环中，我们判断当前情况下是否满足定义，即 right - left + 1 >= citations[left]，如果满足，则说明当前的 H 指数是 citations[left]。

如果不满足，则说明当前的 H 指数是 right - left，我们将 right 指针左移，继续循环，直到找到满足条件的值。

代码实现

def hIndex(citations):

    citations.sort(reverse=True)
    n = len(citations)
    left, right = 0, n - 1
    while left <= right:
        mid = (left + right) // 2
        if citations[mid] == mid + 1:
            return mid + 1
        elif citations[mid] < mid + 1:
            left = mid + 1
        else:
            right = mid - 1
    return left

在上述代码中，我们首先对 citations 数组进行了逆序排序，然后使用二分查找确定 H 指数的范围。

时间复杂度

排序算法的时间复杂度为 O(nlogn)，二分查找算法的时间复杂度为 O(logn)。因此，总的时间复杂度为 O(nlogn)。

空间复杂度

排序算法的空间复杂度为 O(1)，而二分查找算法的空间复杂度也为 O(1)。因此，总的空间复杂度为 O(1)。

总结

LeetCode Algorithm 274. H 指数是一道关于学术论文被引用次数与被引用次数关系的算法题。通过对给定的论文集合进行排序和遍历，我们可以计算出 H 指数。算法的核心思想是使用二分查找的方式，通过比较当前引用次数与论文数量的大小，来确定 H 指数的范围。通过良好的空间和时间优化，我们可以在较短的时间内解决该问题。