0275. H 指数 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 二分查找
• 3. 🔗 引用

1. 📝 题目描述

• leetcode

给你一个整数数组 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^5
• 0 <= citations[i] <= 1000
• citations 按 升序排列

2. 🎯 s.1 - 二分查找

c

int hIndex(int* citations, int citationsSize) {
    int n = citationsSize, lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (citations[mid] >= n - mid) hi = mid - 1;
        else lo = mid + 1;
    }
    return n - lo;
}

js

/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function (citations) {
  const n = citations.length
  let lo = 0,
    hi = n - 1
  while (lo <= hi) {
    const mid = (lo + hi) >> 1
    if (citations[mid] >= n - mid) hi = mid - 1
    else lo = mid + 1
  }
  return n - lo
}

py

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

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

算法思路：

• 数组已升序排列，二分查找第一个满足 citations[mid] >= n - mid 的位置
• n - lo 即为 H 指数

3. 🔗 引用

• h 指数的定义 - 百度百科