274. H 指数

# 题目

## 274. H 指数

[https://leetcode-cn.com/problems/h-index/](https://leetcode-cn.com/problems/h-index/)

给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 *h* 指数。

[h 指数的定义](https://baike.baidu.com/item/h-index/3991452?fr=aladdin)：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）**总共**有 h 篇论文分别被引用了**至少** h 次。且其余的 *N - h* 篇论文每篇被引用次数 **不超过** *h* 次。

例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。

**示例：**

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

**提示：** 如果 *h* 有多种可能的值，*h* 指数是其中最大的那个。

# 题解

## 思路

二分查找，取中间值后，循环判断大于当前值的篇数

## 代码

```javascript
/**
 * @param {number[]} citations
 * @return {number}
 */
// 二分查找
var hIndex = function (citations) {
    let left = 0;
    let right = citations.length;
    let mid;
    let count;
    while (left < right) {
        // 向上取整
        mid = Math.ceil(left + (right - left) / 2);
        count = 0;
        // 满足高引用的特点是：引用次数 >= 论文篇数
        // count 的含义是：大于等于 mid 的论文篇数
        citations.forEach(item => {
            if (item >= mid) {
                count++;
            }
        });
        if (count >= mid) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
};
```

## 参考

### 理解题意

这道问题理解题意要花很长时间，一个有效的办法就是：仔细研究示例，然后去理解题目的意思。我真正明白题目的意思是看到这句描述：

> 例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇。

所以 h 指数是 20 表示：**引用次数大于等于 20 的文章数量最少是 20 篇**。

再来理解一下题目中给出的定义：

> 1. **`N` 篇论文中总共有 `h` 篇论文分别被引用了至少 `h` 次**；
> 2. **其余的 `N - h` 篇论文每篇被引用次数不超过 `h` 次**。

h 指数想说的是这样一件事情：一个人的论文根据被引用的次数，有一个阈值（分水岭，就是这里的 `h`），引用次数大于等于这个阈值的论文是「高引用论文」。

所以理解 h 指数的时候可以把一个研究者的论文被引用的次数 **按照升序排序**。题目其实要我们找的是一条分割线，这条分割线的含义是：分割线右边的所有论文的引用次数都很高，并且：**分割线右边的最少引用次数 >= 分割线右边的论文篇数**。

重要的事情说 3 遍：

h 指数是 **论文数量**，不是引用次数。
h 指数是 **论文数量**，不是引用次数。
h 指数是 **论文数量**，不是引用次数。

**题目要求返回的是论文数量**。再看看题目的示例：

![image.png](/media/202107/2021-07-12_232256.png)

这个例子有点儿特殊，论文被引用了 3 次，篇数有 3 篇。再来看一个更一般的例子：

![image.png](/media/202107/2021-07-12_232256.png)

**结论**：这条分割线越靠左边，说明被引用的次数很多，文章还很多，h 指数越高。

在一个有范围的整数区间里中查找一个位置，可以使用二分查找，这件事情通常区别于「在有序数组里查找一个元素的值」，被称为「二分答案」。

### 方法：二分查找

首先确定整数的范围：

- 最差情况下，所有的论文被引用次数都为 0；
- 最好情况下，所有的论文的引用次数 >= 总共论文篇数。

因此整数区间为 `[0..len]`，这里 `len` 是输入数组的长度。

二分查找先猜一个 **论文篇数** `int mid = (left + right + 1) / 2`（如果不太明白为什么加 1 的朋友，可以暂时先不管，这不重要）。

论文篇数和被引用次数的关系是：「高引用的被引用次数 >= 高引用的论文数」，这些论文才可以被称为「高引用」。因此在二分查找的循环体内部，可以遍历一次数组，数出大于等于 `mid` 的论文篇数。

- 如果大于等于 `mid` 的论文篇数大于等于 `mid` ，说明 h 指数至少是 `mid`。例如 `[0,1,|3,5,6]`，引用次数大于等于 2 的论文有 3 篇，说明答案至少是 2，最终答案落在区间 `[mid..right]` 里，此时设置 `left = mid`；
- 反面的情况不用思考，因为只要上面分析对了，最终答案落在区间 `[mid..right]` 的反面区间 `[left..mid - 1]` 里，此时设置 `right = mid - 1`。

**参考代码**：

- Java

```
public class Solution {

public int hIndex(int[] citations) {
        int len = citations.length;
        int left = 0;
        int right = len;
        while (left < right) {
            // 猜论文篇数
            int mid = (left + right + 1) / 2;
            // 满足高引用的特点是：引用次数 >= 论文篇数
            // count 的含义是：大于等于 mid 的论文篇数
            int count = 0;
            for (int citation : citations) {
                if (citation >= mid) {
                    count++;
                }
            }

if (count >= mid) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}
```

**说明**：

- `while (left < right)` 与 `left = mid`、`right = mid - 1` 配合使用表示退出循环以后有 `left == right` 成立；
- 看到 `left = mid` 与 `right = mid - 1` ，取 `int mid = (left + right) / 2` 的时候就需要上取整，因此加 1，原因在 [题解](https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/)），如果不想看那么多东西，简单一句话，就是为了避免死循环；
- 退出循环以后，`left` 就来到了合适的位置，题目要返回的是论文篇数，所以需要返回 `len - left`；
- 可以翻到英文题面，最后有给数据范围， `int mid = (left + right + 1) / 2;` 写成这样是因为题目给出的数据范围不会使得 `left + right` 越界，所以不写成 `int mid = left + (right -left + 1) / 2;`，写代码尽量写本来想表达的意思。

**复杂度分析**：

- 时间复杂度：O(Nlog N)，二分循环 log N 次，每一次都需要看一遍数组；
- 空间复杂度：O(1)，只使用了常数个变量。