英文原文
Given an array of integers citations
where citations[i]
is the number of citations a researcher received for their ith
paper, return compute the researcher's h
-index.
According to the definition of h-index on Wikipedia: A scientist has an index h
if h
of their n
papers have at least h
citations each, and the other n − h
papers have no more than h
citations each.
If there are several possible values for h
, the maximum one is taken as the h
-index.
Example 1:
Input: citations = [3,0,6,1,5] Output: 3 Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.
Example 2:
Input: citations = [1,3,1] Output: 1
Constraints:
n == citations.length
1 <= n <= 5000
0 <= citations[i] <= 1000
中文题目
给你一个整数数组 citations
,其中 citations[i]
表示研究者的第 i
篇论文被引用的次数。计算并返回该研究者的 h
指数。
h 指数的定义:h 代表“高引用次数”(high citations),一名科研人员的 h 指数是指他(她)的 (n
篇论文中)总共有 h
篇论文分别被引用了至少 h
次。且其余的 n - h
篇论文每篇被引用次数 不超过 h
次。
例如:某人的 h 指数是 20,这表示他已发表的论文中,每篇被引用了至少 20 次的论文总共有 20 篇。
提示:如果 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.length
1 <= n <= 5000
0 <= citations[i] <= 1000
通过代码
高赞题解
模拟 + 二分
根据题意,我们需要找到满足条件「引用次数至少为 $x$ 次的 $x$ 篇论文」中的最大 $x$ 值。
那么在以最大值 $x$ 为分割点的正整数数轴上,满足二段性:
- 少于等于 $x$ 的数值必然满足条件;
- 大于 $x$ 的数值必然不满足。
因此我们可以通过二分在 $[0, n]$ 范围内找分割点 $x$。
代码:
class Solution {
public int hIndex(int[] cs) {
int n = cs.length;
int l = 0, r = n;
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(cs, mid)) l = mid;
else r = mid - 1;
}
return r;
}
boolean check(int[] cs, int mid) {
int ans = 0;
for (int i : cs) if (i >= mid) ans++;
return ans >= mid;
}
}
- 时间复杂度:对 $[0, n]$ 做二分,复杂度为 $O(\log{n})$;
check
函数需要对数组进行线性遍历,复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$ - 空间复杂度:$O(1)$
其他「二分」相关内容
【重点】不太清楚 check
的大于小于怎么确定的可以重点看看这篇
- 二分 check 函数如何确定
34. 在排序数组中查找元素的第一个和最后一个位置 : 考察对「二分」的理解,以及 check 函数的「大于 小于」怎么写
题目 | 题解 | 难度 | 推荐指数 |
---|---|---|---|
4. 寻找两个正序数组的中位数 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩 |
29. 两数相除 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
33. 搜索旋转排序数组 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩🤩 |
34. 在排序数组中查找元素的第一个和最后一个位置 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩🤩 |
35. 搜索插入位置 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩🤩 |
74. 搜索二维矩阵 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
81. 搜索旋转排序数组 II | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
153. 寻找旋转排序数组中的最小值 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
154. 寻找旋转排序数组中的最小值 II | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
220. 存在重复元素 III | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
278. 第一个错误的版本 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
354. 俄罗斯套娃信封问题 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
363. 矩形区域不超过 K 的最大数值和 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
374. 猜数字大小 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
778. 水位上升的泳池中游泳 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
852. 山脉数组的峰顶索引 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩🤩 |
981. 基于时间的键值存储 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
1004. 最大连续1的个数 III | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
1011. 在 D 天内送达包裹的能力 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
1208. 尽可能使字符串相等 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
1438. 绝对差不超过限制的最长连续子数组 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
1482. 制作 m 束花所需的最少天数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
1707. 与数组中元素的最大异或值 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
1751. 最多可以参加的会议数目 II | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
统计信息
通过次数 | 提交次数 | AC比率 |
---|---|---|
55815 | 126792 | 44.0% |
提交历史
提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
---|
相似题目
题目 | 难度 |
---|---|
H 指数 II | 中等 |