0275-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：

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

提示：

• n == citations.length
• 1 <= n <= 105
• 0 <= citations[i] <= 1000
• citations 按 升序排列

前言

这道题是「274. H 指数 」的延伸，和第 274 题相比，这道题中的输入数组 $\textit{citations}$ 已经按照升序排序。

除了使用第 274 题的方法以外（见「274. H 指数的官方题解 」），这道题可以利用数组 $\textit{citations}$ 有序的特点，使用二分查找的方法求解，时间复杂度为 $O(\log n)$，其中 $n$ 为数组 $\textit{citations}$ 的长度。

方法一：二分查找

由于数组 $\textit{citations}$ 已经按照升序排序，因此可以使用二分查找。

设查找范围的初始左边界 $\textit{left}$ 为 $0$, 初始右边界 $\textit{right}$ 为 $n-1$，其中 $n$ 为数组 $\textit{citations}$ 的长度。每次在查找范围内取中点 $\textit{mid}$，则有 $n-\textit{mid}$ 篇论文被引用了至少 $\textit{citations}[\textit{mid}]$ 次。如果在查找过程中满足 $\textit{citations}[\textit{mid}] \ge n - \textit{mid}$，则移动右边界 $\textit{right}$，否则移动左边界 $\textit{left}$。

[sol1-Java]

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] >= n - mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return n - left;
    }
}

[sol1-C#]

public class Solution {
    public int HIndex(int[] citations) {
        int n = citations.Length;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] >= n - mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return n - left;
    }
}

[sol1-Python3]

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

[sol1-JavaScript]

var hIndex = function(citations) {
    let n = citations.length;
    let left = 0, right = n - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (citations[mid] >= n - mid) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return n - left;
};

[sol1-C++]

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] >= n - mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return n - left;
    }
};

[sol1-C]

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

[sol1-Golang]

func hIndex(citations []int) int {
    n := len(citations)
    return n - sort.Search(n, func(x int) bool { return citations[x] >= n-x })
}

复杂度分析

• 时间复杂度：$O(\log n)$，其中 $n$ 为数组 $\textit{citations}$ 的长度。二分查找的时间复杂度为 $O(\log n)$。

• 空间复杂度：$O(1)$。