【面试高频题】难度 1.5/5，简单修改条件的阅读理解题

题目描述

这是 LeetCode 上的「275. H 指数 II」，难度为「中等」。

Tag : 「二分」、「数学」

给你一个整数数组 citations，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照「升序排列」。计算并返回该研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。

请你设计并实现对数时间复杂度的算法解决此问题。

示例 1：

代码语言：javascript复制

输入：citations = [0,1,3,5,6]

输出：3 

解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3 。

示例 2：

代码语言：javascript复制

输入：citations = [1,2,100]

输出：2

提示：

n = citations.length

1 <= n <= 10^5

0 <= citations[i] <= 1000

• citations 按升序排列

与前置题关系

本题与前置题 274. H 指数 的不同，主要体现在两个方面：

1. 数据范围不同：在 274. H 指数 里

n

的范围为

5000

，而本题

n

的范围为

10^5

；

1. 数组是否有序：在 274. H 指数 中数组不确保有序，本题则是有序。

增加了数组有序特性，又扩大了数据范围。

容易联想，利用此特性，存在复杂度更低的算法。

基本分析

为了方便，将 citations 记为 cs。

所谓的 h 指数是指一个具体的数值，该数值为“最大”的满足「至少发表了 x 篇论文，且每篇论文至少被引用 x 次」定义的合法数，重点是“最大”。

用题面的实例

1

来举个