0274. H 指数
大约 2 分钟
---
0274. 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
解题思路
思路 1:排序 + 遍历
这是一个经典的 H 指数计算问题。我们需要找到一个最大的 值,使得至少有 篇论文的引用次数大于等于 。
核心思想是:
- 将引用次数数组 按照降序排列。
- 从大到小遍历排序后的数组,找到第一个满足 的位置。
- 此时 指数就是 ,表示有 篇论文的引用次数大于等于 。
具体算法步骤:
- 对数组 进行降序排序:。
- 初始化 。
- 遍历排序后的数组,对于每个位置 :
- 如果 ,说明至少有 篇论文的引用次数大于等于 ,更新 。
- 否则,停止遍历。
- 返回 指数。
思路 1:代码
class Solution:
def hIndex(self, citations: List[int]) -> int:
# 对引用次数数组进行降序排序
citations.sort(reverse=True)
# 初始化 h 指数为 0
h = 0
# 遍历排序后的数组
for i in range(len(citations)):
# 如果当前论文的引用次数大于等于 i+1
# 说明至少有 i+1 篇论文的引用次数大于等于 i+1
if citations[i] >= i + 1:
h = i + 1
else:
# 一旦不满足条件,就可以停止遍历
break
return h
思路 1:复杂度分析
- 时间复杂度:,其中 是数组长度。主要时间消耗在排序操作上。
- 空间复杂度:,只使用了常数额外空间。