C++ 中的 H 指数 II

C++ 中的H指数 II问题是经典 H指数问题的一个变体，专门设计用于处理排序数组。H指数是衡量研究人员的生产力和引用影响力的指标，目标是找到最大的数字 h，使得研究人员至少有 h 篇论文，每篇论文的引用次数至少为 h。

问题概述

给定一个非负整数的排序数组 citations[]，其中每个元素表示研究人员某篇论文获得的引用次数，任务是确定研究人员的 H 指数。数组按升序排序，你需要找到 h 的最大值，使得至少有 h 篇论文的引用次数大于或等于 h。

方法 1：简单方法

输出

 
The H-Index is: 3   

说明

步骤 1：输入和初始化

• 问题提供了一个排序的整数列表，其中每个整数代表一篇论文获得的引用次数。列表的长度 n，告诉我们总共有多少篇论文。我们的目标是找到 h 的最大值，使得至少有 h 篇论文的引用次数大于或等于 h。
• 我们开始设置两个指针：low 和 high。low 指针设置在列表的开头（索引 0），high 指针设置在列表的末尾（索引 n-1）。这两个指针定义了我们将要搜索正确 h 值的范围。

步骤 2：二分查找循环

• 现在，我们使用二分查找来高效地缩小 H 指数可能存在的范围。我们通过取 low 和 high 的平均值来计算列表中的中点，称为 mid。这给了我们 mid 位置的一篇论文，以及该论文的引用次数。
• 对于 mid 位置的每篇论文，我们还计算有多少篇论文的引用次数大于或等于 mid 论文的引用次数。这是通过计算 n - mid 来实现的，它告诉我们 mid 之后有多少篇论文（包括 mid 本身）。

步骤 3：条件检查

• 在计算了满足引用次数阈值的论文数量后，我们检查它是否与 mid 论文的引用次数匹配。这是解决方案的核心。
• 如果文档数量 n - mid 等于 mid 论文的引用次数，我们就找到了 H 指数。这是因为引用次数至少为 h 的文档数量恰好等于引用次数，满足了 H 指数的定义。
• 如果具有足够引文的论文数量少于引用次数，则意味着我们需要在列表的左侧进行搜索。在这种情况下，我们将 high 指针向左移动以缩小搜索范围。
• 如果具有足够引文的论文数量多于引用次数，则意味着我们需要在列表的右侧进行搜索。因此，我们将 low 指针向右移动，从而在该方向上扩展我们的搜索。

步骤 4：搜索完成

• 二分查找继续进行，根据比较调整 low 和 high 来缩小搜索范围，直到指针收敛并且搜索终止。如果在搜索过程中没有找到完全匹配，则最终结果取决于 low 指针最后一个位置能够满足 h 指数条件的论文数量。

步骤 5：返回 H 指数

• 在二分查找结束时，H 指数是根据搜索收敛的位置计算的。具体来说，n - low 的值给出了至少有这么多引文的论文的最大数量，这代表了 H 指数。

时间复杂度

• 二分查找：在每一步中，搜索空间都会减半，这意味着算法不需要扫描列表中的所有 n 个元素，而是执行大约 log n 步（其中 n 是论文的数量）。
• 由于在每一步中，我们只将中点元素与其对应的引用值进行比较，因此总时间复杂度为 O(log n)。

空间复杂度

• 该算法仅使用常数量的额外空间用于 low、high、mid 等变量以及一些其他临时值。没有使用额外的数据结构（如数组或列表）。
• 因此，空间复杂度为 O(1)，即常数空间，这意味着它不会随着输入大小的增加而增长。

方法 2：使用线性扫描方法

由于数组已经排序，一种简单的方法是遍历数组一次并直接计算 H 指数。这种方法以牺牲效率为代价来换取简单性，因为它避免了二分查找的复杂性。

输出

 
The H-Index is: 3   

说明

理解输入

• 您将获得每篇论文的引用列表，按升序排序。这意味着引用次数较少的论文排在引用次数较多的论文之前。

遍历策略

• 该方法涉及从头到尾遍历列表。在遍历过程中，您将确定有多少篇论文至少具有一定数量的引用。目标是找到满足“至少有 h 篇论文的引用次数大于或等于 h”条件的最高 h 值。

计算具有足够引文的论文数量

• 对于列表中的每个位置，考虑该位置的引用值。此引用值表示论文被考虑所需的最低引用次数。
• 计算至少具有此引用次数的论文数量。由于列表已排序，这只是文档总数减去当前索引。例如，如果您处于索引 i，那么从索引 i 到列表末尾（包括索引 i 本身）共有 n - i 篇论文。

检查条件

• 将当前引用值与计算出的需要至少拥有该数量引文的文档数量进行比较。
• 如果当前索引处的引用值大于或等于需要至少拥有该数量引文的论文数量，则此引用值可能是一个有效的 H 指数。将此值作为结果返回。

继续扫描

• 如果条件不满足，则移动到下一个索引并重复此过程。继续此过程，直到找到有效的 H 指数或扫描完列表。

处理边缘情况

• 如果在扫描完整个列表而没有找到有效的 H 指数，则表示不存在满足“具有 h 篇引文的论文数量足够”的 h。在这种情况下，返回 0 作为 H 指数。

复杂度分析

时间复杂度

O(n)：在线性扫描方法中，您只遍历一次引用列表。每一步都涉及简单的算术运算和比较，因此时间复杂度与引用的数量成线性关系。

空间复杂度

O(1)：该方法使用常数量的额外空间。您只需要几个变量来跟踪当前索引和结果。除此之外，不需要额外的数据结构或内存分配。

方法 3：使用基于计数排序的方法

这种方法类似于计数排序，您计算有多少篇论文具有特定数量的引用，然后累积这些计数以找到 H 指数。如果引用值不是太大，这种方法效果很好。

实施

输出

 
The H-Index is: 3   

说明

输入和初始化

• 您收到多篇论文的引用计数列表，已排序或未排序。假设文档总数为 n。
• 您需要创建一个计数数组（count array），其中每个索引表示有多少篇论文具有特定数量的引用。此数组将有助于跟踪每个引用值的出现频率。

计算引用出现次数

• 在引用列表中，对于每个引用，增加计数数组中与引用次数匹配的位置的值。
• 如果一篇论文的引用次数大于 n（这意味着引用的数量多于论文的总数），则将其计数限制为 n，因为引用次数多于论文数量不会影响 H 指数。
• 例如，如果您有 n 篇论文，请创建一个大小为 n + 1 的计数数组。如果一篇论文有五个引用，则递增索引 5 处的值。如果一篇论文的引用次数大于 n，则递增最后一个索引（n）。

从高到低累积计数

• 一旦计数数组填充完毕，我们就需要确定对于每个可能的 i，有多少篇论文至少有 i 篇引用。
• 为此，从最大的索引（即最大可能的引用计数，为 n）开始，然后向下移动。
• 对于每个索引，累积具有该数量或更多引用的论文数量。这有助于跟踪有多少篇论文至少有一定数量的引用。
• 当您从高引用值移到低引用值时，您实际上是在累加满足或超过该引用计数的论文数量。

H 指数条件

• 目标是找到最大的 i，使得至少有 i 篇论文的引用次数大于或等于 i。因此，在累积计数时，请检查累积计数（即引用次数大于或等于 i 的论文数量）是否大于或等于 i。
• 一旦满足此条件，i 就是您的 H 指数。

边缘情况

• 如果没有找到满足“至少有 i 篇论文的引用次数大于或等于 i”条件的索引，则 H 指数为 0。这种情况会发生在没有任何文档的引用次数足以满足 H 指数的最低条件时。

复杂度分析

时间复杂度

O(n)：基于计数排序的方法遍历引用列表一次以填充计数数组，然后遍历计数数组一次以计算 H 指数。

填充计数数组需要 O(n) 时间，其中 n 是论文的数量。

累积计数以确定 H 指数也需要 O(n) 时间，因为计数数组的大小为 n + 1。

因此，总时间复杂度为 O(n)。

空间复杂度

O(n)：空间复杂度主要由计数数组决定，其大小为 n + 1，其中 n 是论文的数量。由于没有使用其他数据结构，因此空间复杂度相对于文档数量保持线性。