LC 275. H 指数 II

题目描述

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

给你一个整数数组 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：

1
2
3

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

输出：2

提示：

$n = citations.length$
$1 <= n <= 10^5$
$0 <= citations[i] <= 1000$
citations 按升序排列

与前置题关系

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

数据范围不同：在 274. H 指数里 $n$ 的范围为 $5000$，而本题 $n$ 的范围为 $10^5$；
数组是否有序：在 274. H 指数中数组不确保有序，本题则是有序。

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

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

基本分析

为了方便，将 citations 记为 cs。

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

用题面的实例 $1$ 来举个 🌰，给定所有论文的引用次数情况为 cs = [0,1,3,5,6]，可统计满足定义的数值有哪些：

$h = 0$，含义为「至少发表了 $0$ 篇，且这 $0$ 篇论文至少被引用 $0$ 次」，空集即满足，恒成立；
$h = 1$，含义为「至少发表了 $1$ 篇，且这 $1$ 篇论文至少被引用 $1$ 次」，可以找到这样的组合，如 [1]，成立；
$h = 2$，含义为「至少发表了 $2$ 篇，且这 $2$ 篇论文至少被引用 $2$ 次」，可以找到这样的组合，如 [3, 5]，成立；
$h = 3$，含义为「至少发表了 $3$ 篇，且这 $3$ 篇论文至少被引用 $3$ 次」，可以找到这样的组合，如 [3, 5, 6]，成立；
$h = 4$，含义为「至少发表了 $4$ 篇，且这 $4$ 篇论文至少被引用 $4$ 次」，找不到这样的组合，不成立；
…

实际上，当遇到第一个无法满足的数时，更大的数值就没必要找了。一个简单的推导：

至少出现 $k$ 次的论文数不足 $k$ 篇 => 至少出现 $k + 1$ 次的论文必然不足 $k$ 篇 => 至少出现 $k + 1$ 次的论文必然不足 $k + 1$ 篇（即更大的 $h$ 不满足）。

计数

首先，仍能使用「计数」的方式进行求解，该求解为线性复杂度，且不要求数组有序。

根据分析，最大的 h 不超过 $n$。

假设我们预处理出引用次数所对应的论文数量 cnt，其中 cnt[a] = b 含义为引用次数恰好为 a 的论文数量有 b 篇。

那么再利用 h 是“最大”的满足定义的合法数，我们从 $n$ 开始往前找，找到的第一个满足条件的数，即是答案。

具体的，创建 cnt 数组，对 cs 进行计数，由于最大 h 不超过 $n$，因此对于引用次数超过 $n$ 的论文，可等价为引用次数为 $n$，即有计数逻辑 cnt[min(c, n)]++。

再根据处理好的 cnt，从 $n$ 开始倒序找 h。

由于我们处理的 cnt[a] 含义为引用次数恰好为 a，但题目定义则是至少。同时「至少出现 $k + 1$ 次」的集合必然慢「至少出现 $k$ 次」要求（子集关系），我们可以使用变量 tot，对处理过的 cnt[i] 进行累加，从而实现从恰好到至少的转换。

Java 代码：

class Solution {
    public int hIndex(int[] cs) {
        int n = cs.length;
        int[] cnt = new int[n + 10];
        for (int c : cs) cnt[Math.min(c, n)]++;
        for (int i = n, tot = 0; i >= 0; i--) {
            tot += cnt[i];
            if (tot >= i) return i;
        }
        return -1; // never
    }
}

C++ 代码：

class Solution {
public:
    int hIndex(vector<int>& cs) {
        int n = cs.size();
        vector<int> cnt(n + 10, 0);
        for (int c : cs) cnt[min(c, n)]++;
        for (int i = n, tot = 0; i >= 0; i--) {
            tot += cnt[i];
            if (tot >= i) return i;
        }
        return -1; // never
    }
};

Python 代码：

class Solution:
    def hIndex(self, cs: List[int]) -> int:
        n = len(cs)
        cnt = [0] * (n + 10)
        for c in cs:
            cnt[min(c, n)] += 1
        tot = 0
        for i in range(n, -1, -1):
            tot += cnt[i]
            if tot >= i:
                return i
        return -1  # never

TypeScript 代码：

function hIndex(cs: number[]): number {
    const n = cs.length;
    const cnt = new Array(n + 10).fill(0);
    for (let c of cs) cnt[Math.min(c, n)]++;
    for (let i = n, tot = 0; i >= 0; i--) {
        tot += cnt[i];
        if (tot >= i) return i;
    }
    return -1; // never
};

时间复杂度：$O(n)$
空间复杂度：$O(n)$

二分答案（线性 `check`）

除了线性复杂度的「计数」做法，我们还容易想到「二分」。

其中最容易想到的是「二分答案」，该做法复杂度为 $O(n\log{n})$，同样并不要求数组有序。

我们发现对于任意的 cs（论文总数量为该数组长度 $n$），都必然对应了一个最大的 h 值，且小于等于该 h 值的情况均满足，大于该 h 值的均不满足。

那么，在以最大 h 值为分割点的数轴上具有「二段性」，可通过「二分」求解该分割点（答案）。

最后考虑在什么值域范围内进行二分？

一个合格的二分范围，仅需确保答案在此范围内即可。

再回看我们关于 h 的定义「至少发表了 x 篇论文，且每篇论文至少被引用 x 次」，满足条件除了引用次数，还有论文数量，而总的论文数量只有 $n$，因此最大的 h 只能是 $n$ 本身，而不能是比 $n$ 大的数，否则论文数量就不够了。

综上，我们只需要在 $[0, n]$ 范围进行二分即可。对于任意二分值 mid，只需线性扫描 cs 即可知道其是否合法。

Java 代码：

class Solution {
    public int hIndex(int[] cs) {
        int n = cs.length;
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (check(cs, mid)) l = mid;
            else r = mid - 1;
        }
        return r;
    }
    boolean check(int[] cs, int mid) {
        int ans = 0;
        for (int i : cs) if (i >= mid) ans++;
        return ans >= mid;
    }
}

C++ 代码：

class Solution {
public:
    int hIndex(vector<int>& cs) {
        int n = cs.size();
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (check(cs, mid)) l = mid;
            else r = mid - 1;
        }
        return r;
    }
    bool check(vector<int>& cs, int x) {
        int cnt = 0;
        for (int c : cs) {
            if (c >= x) cnt++;
        }
        return cnt >= x;
    }
};

Python 代码：

class Solution:
    def hIndex(self, cs: List[int]) -> int:
        n = len(cs)
        l, r = 0, n
        while l < r:
            mid = (l + r + 1) // 2
            if sum(c >= mid for c in cs) >= mid:
                l = mid
            else:
                r = mid - 1
        return r

TypeScript 代码：

function hIndex(cs: number[]): number {
    const check = function (cs: number[], x: number): boolean {
        let cnt: number = 0;
        for (let c of cs) {
            if (c >= x) cnt++;
        }
        return cnt >= x;
    }
    const n = cs.length;
    let l = 0, r = n;
    while (l < r) {
        const mid = Math.floor((l + r + 1) / 2);
        if (check(cs, mid)) l = mid;
        else r = mid - 1;
    }
    return r;
};

时间复杂度：对 $[0, n]$ 做二分，复杂度为 $O(\log{n})$；check 函数需要对数组进行线性遍历，复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
空间复杂度：$O(1)$

二分下标（根据与 $cs[i]$ 关系）

在上述二分中，我们没有利用本题的「数组有序」的特性。

根据对 h 定义，若 $cs$ 升序，我们可推导出：

在最大的符合条件的分割点 $x$ 的右边（包含分割点），必然满足 $cs[i] >= x$
在最大的符合条件的分割点 $x$ 的左边，必然不满足 $cs[i] >= x$

因此，我们可以利用 分割点右边数的个数与分割点 $cs[x]$ 的大小关系进行二分 。

假设存在真实分割点下标 $x$，其值大小为 $cs[x]$，分割点右边的数值个数为 $n - x$，根据 H 指数 的定义，必然有 $cs[x] >= n - x$ 关系：

在分割点 $x$ 的右边：$cs[i]$ 非严格单调递增，数的个数严格单调递减，仍然满足 $cs[i] >= n - i$ 关系；
在分割点 $x$ 的左边：$cs[i]$ 非严格单调递减，数的个数严格单调递增，$x$ 作为真实分割点，必然不满足 $cs[i] >= n - i$ 关系。

利用此「二段性」进行二分即可，二分出下标后，再计算出数的个数。

Java 代码：

class Solution {
    public int hIndex(int[] cs) {
        int n = cs.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (cs[mid] >= n - mid) r = mid;
            else l = mid + 1;
        }
        return cs[r] >= n - r ? n - r : 0;
    }
}

C++ 代码：

class Solution {
public:
    int hIndex(vector<int>& cs) {
        int n = cs.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (cs[mid] >= n - mid) r = mid;    
            else l = mid + 1;
        }
        return cs[r] >= n - r ? n - r : 0;
    }
};

Python 代码：

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

TypeScript 代码：

function hIndex(cs: number[]): number {
    const n = cs.length;
    let l = 0, r = n - 1;
    while (l < r) {
        const mid = l + r >> 1;
        if (cs[mid] >= n - mid) r = mid;
        else l = mid + 1;
    }
    return cs[r] >= n - r ? n - r : 0;
};

时间复杂度：$O(\log{n})$
空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.275 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

二分数学

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 2003. 每棵子树内缺失的最小基因值上一篇

LC 274. H 指数下一篇

LC 275. H 指数 II

题目描述

与前置题关系

基本分析

计数

二分答案（线性 check）

二分下标（根据与 $cs[i]$ 关系）

最后

二分答案（线性 `check`）