What is the H-Index II problem on LeetCode?

H-Index II asks for the maximum h where a sorted array of citations has at least h papers with h or more citations, requiring logarithmic runtime.

Why use binary search for H-Index II?

Binary search efficiently narrows down the valid H-Index in a sorted array, avoiding the need for linear scans and achieving O(log n) time.

How do I check if a candidate h is valid?

Compute n - index at the midpoint of the search; if this is >= h, the candidate h is valid and you search higher.

What are common mistakes when implementing H-Index II?

Mistakes include miscounting papers, off-by-one errors in binary search, and using linear iteration instead of O(log n) search.

Can H-Index II be solved if citations are unsorted?

Yes, but you must first sort the array; otherwise, binary search over the valid answer space cannot guarantee correctness.

#275

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

H 指数 II

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数， citations 已经按照非降序排列。计算并返回该研究者的 h 指数。 h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她…

数组二分查找

题目描述

给你一个整数数组 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.length
1 <= n <= 10⁵
0 <= citations[i] <= 1000
citations 按 升序排列

lightbulb

解题思路

方法一：二分查找

我们注意到，如果有至少 $x$ 篇论文的引用次数大于等于 $x$ ，那么对于任意 $y \lt x$ ，其引用次数也一定大于等于 $y$ 。这存在着单调性。

因此，我们二分枚举 $h$ ，获取满足条件的最大 $h$ 。由于要满足 $h$ 篇论文至少被引用 $h$ 次，因此 $citations[n - mid] \ge mid$ 。

时间复杂度 $O(\log n)$ ，其中 $n$ 是数组 $citations$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        left, right = 0, n
        while left < right:
            mid = (left + right + 1) >> 1
            if citations[n - mid] >= mid:
                left = mid
            else:
                right = mid - 1
        return left

speed

复杂度分析

指标	值
时间	complexity is O(log n) due to binary search over possible H-Index values. Space complexity is O(1) as only a few variables are maintained during search.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expecting logarithmic time using the sorted property of citations.
question_mark
Looking for correct identification of the H-Index without linear scanning.
question_mark
Check for off-by-one errors in determining n - index >= h condition.

warning

常见陷阱

外企场景

error
Confusing index positions with citation counts during binary search.
error
Failing to handle cases where citations are all lower than potential h.
error
Using linear scan, which violates the logarithmic time requirement.

swap_horiz

进阶变体

外企场景

arrow_right_alt
H-Index calculation where the citations array is unsorted, requiring sorting first.
arrow_right_alt
Dynamic H-Index tracking as new citations are added to the array.
arrow_right_alt
Compute H-Index with additional constraints, e.g., only counting papers from certain journals.

help

常见问题

外企场景

继续练习

#268 丢失的数字 #287 寻找重复数 #300 最长递增子序列