274 H指数

相关链接

LeetCode 274 H指数

题目描述

给定一个整数数组 citations，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。需要计算并返回该研究者的 h 指数。

H 指数定义

根据维基百科上的定义，h 代表“高引用次数”。一名科研人员的 h 指数是指他（她）至少发表了 h 篇论文，并且至少有 h 篇论文被引用次数大于等于 h。如果 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

思路

1. 由于数组元素最大值为 1000，从后向前循环遍历数组，每趟计算是否存在大于等于 i 的数字 i 个。
2. 二分查找：设查找范围的初始左边界 left 为 0，初始右边界 right 为 n。每次在查找范围内取中点 mid，同时扫描整个数组，判断是否至少有 mid 个数大于 mid。如果有，说明要寻找的 h 在搜索区间的右边，反之则在左边。

代码实现

方法 1: 线性扫描

public int hIndex(int[] citations) {
    for (int i = 1000; i >= 0; i--) {
        int finalI = i;
        int res = (int) Arrays.stream(citations).filter(num -> num >= finalI).count();
        if (res >= finalI) {
            return i;
        }
    }
    return 0;
}

方法 2: 二分查找

public int hIndex(int[] citations) {
    int left = 0, right = citations.length;
    while (left < right) {
        int mid = (left + right + 1) >> 1;
        int times = 0;
        for (int citation : citations) {
            if (citation >= mid) {
                times++;
            }
        }
        if (times >= mid) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}