H 指数 II
难度:
标签:
题目描述
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。
h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。
请你设计并实现对数时间复杂度的算法解决此问题。
示例 1：
输入：citations = [0,1,3,5,6]输出：3解释：给定数组表示研究者总共有5篇论文，每篇论文相应的被引用了0, 1, 3, 5, 6次。 由于研究者有3篇论文每篇 至少 被引用了3次，其余两篇论文每篇被引用 不多于3次，所以她的 h 指数是3。
示例 2：
输入：citations = [1,2,100]输出：2
提示：
n == citations.length1 <= n <= 1050 <= citations[i] <= 1000citations按 升序排列
代码结果
运行时间: 22 ms, 内存: 21.2 MB
/*
* 思路：
* 使用 Java Stream 可以实现简化版本，但由于二分查找的特性，还是需要手动控制循环。
* 结合 IntStream 和二分查找算法来实现。
*/
import java.util.stream.IntStream;
public class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
return IntStream.range(0, n)
.map(i -> citations[n - 1 - i] >= i + 1 ? 1 : 0)
.reduce((acc, cur) -> acc + cur)
.orElse(0);
}
}解释
方法:
该题解使用了二分查找的方法。由于数组 citations 已经按照升序排列，我们可以二分搜索数组，寻找最大的 h 指数。我们维护左右指针 l 和 r，每次取中间位置 mid，如果 citations[-mid] >= mid，说明至少有 mid 篇论文的引用数 >= mid，满足 h 指数的定义，我们将左指针 l 更新为 mid；否则说明 mid 值偏大，将右指针 r 更新为 mid-1。最终左右指针相遇时的位置即为最大的 h 指数。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在二分查找中使用`citations[-mid] >= mid`作为条件来判断是否满足h指数的要求？
▷🦆
在二分搜索过程中，为什么选择将左指针更新为`mid`而不是`mid+1`当`citations[-mid] >= mid`条件满足时？
▷🦆
如何理解题解中提到的`左右指针相遇时的位置即为最大的 h 指数`，具体是如何保证这一点的？
▷🦆
如果数组`citations`中所有值都为0，二分查找的逻辑是否仍然正确，并能正确返回h指数为0？
▷相关问题
H 指数
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。
示例 1：
输入：citations = [3,0,6,1,5]输出：3 解释：给定数组表示研究者总共有5篇论文，每篇论文相应的被引用了3, 0, 6, 1, 5次。 由于研究者有3篇论文每篇 至少 被引用了3次，其余两篇论文每篇被引用 不多于3次，所以她的 h 指数是3。
示例 2：
输入：citations = [1,3,1] 输出：1
提示：
n == citations.length1 <= n <= 50000 <= citations[i] <= 1000