Medium

题目描述

给你一个整数数组 citations，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数 的定义：h 指数是指该研究者至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中的 最大值。

你必须设计并实现时间复杂度为 O(log n) 的算法。

示例 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 按 升序排列

**要求：**期望运行时间复杂度为 O(log n)，且输入数据已经排序。

解题思路

解题思路

核心思想： 由于数组已排序且要求 O(log n) 时间复杂度，这提示我们使用二分查找。

关键观察： 对于位置 i 的论文，如果 citations[i] >= n-i，则说明从位置 i 开始到数组末尾的所有论文（共 n-i 篇）的引用次数都 >= n-i，这意味着至少有 n-i 篇论文被引用了至少 n-i 次。

二分查找策略：

  1. 寻找满足条件 citations[i] >= n-i 的最小位置 i
  2. 该位置对应的 h 指数就是 n-i
  3. 如果所有位置都不满足条件，h 指数为 0

算法步骤：

  • 使用二分查找在排序数组中寻找第一个满足 citations[mid] >= n-mid 的位置
  • 如果找到这样的位置，h 指数为 n-mid
  • 如果没有找到，说明 h 指数为 0

这种方法巧妙地利用了数组已排序的特性，通过二分查找快速定位关键位置。

时间复杂度： O(log n)，满足题目要求 空间复杂度： O(1)，只使用常数额外空间

代码实现

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;
    }
};

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        n = len(citations)
        left, right = 0, 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

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;
    }
}

var hIndex = function(citations) {
    const n = citations.length;
    let left = 0, right = n - 1;
    
    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2);
        if (citations[mid] >= n - mid) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return n - left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)二分查找的时间复杂度
空间复杂度O(1)只使用常数额外空间

相关题目