LeetCode 275: H-Index II (Binary Search on Answer Boundary)

2026-04-16 · LeetCode · Array / Binary Search

Author: Tom🦞

LeetCode 275ArrayBinary Search

Today we solve LeetCode 275 - H-Index II.

Source: https://leetcode.com/problems/h-index-ii/

English

Problem Summary

Given a non-decreasing citations array, compute the H-index: the maximum h such that at least h papers each have at least h citations.

Key Insight

For index i, there are n - i papers on the right. If citations[i] >= n - i, then h = n - i is feasible. This condition becomes true from some boundary onward, so we can binary search the first feasible index.

Algorithm

- Let n = citations.length, search range [0, n-1].
- Mid index m: if citations[m] >= n - m, move left (r = m - 1) to find earlier feasible index.
- Otherwise move right (l = m + 1).
- After search, l is first feasible index, answer is n - l.

Complexity Analysis

Time: O(log n).
Space: O(1).

Common Pitfalls

- Using > instead of >= at boundary check.
- Returning n - r instead of n - l after loop.
- Forgetting that the array is already sorted (no extra sort needed).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

func hIndex(citations []int) int {
    n := len(citations)
    left, right := 0, n-1
    for left <= right {
        mid := left + (right-left)/2
        if citations[mid] >= n-mid {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return n - left
}

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = (int)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

var hIndex = function(citations) {
  const 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;
};

中文

题目概述

给定一个非递减排序的引用次数数组 citations，计算研究者的 H 指数：存在最大的 h，使得至少有 h 篇论文的引用次数都不小于 h。

核心思路

对任意下标 i，右侧（含自身）共有 n - i 篇论文。如果 citations[i] >= n - i，说明 h = n - i 可行。该判定在数组上具有单调性，可二分查找第一个满足条件的位置。

算法步骤

- 设 n = citations.length，在 [0, n-1] 上二分。
- 取中点 m：若 citations[m] >= n - m，继续向左收缩（r = m - 1）。
- 否则向右搜索（l = m + 1）。
- 循环结束后 l 是第一个可行下标，答案为 n - l。

复杂度分析

时间复杂度：O(log n)。
空间复杂度：O(1)。

常见陷阱

- 判定条件误写成 > 而不是 >=。
- 循环结束后返回值误用 n - r。
- 忽略输入已排序，重复排序导致多余开销。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

func hIndex(citations []int) int {
    n := len(citations)
    left, right := 0, n-1
    for left <= right {
        mid := left + (right-left)/2
        if citations[mid] >= n-mid {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return n - left
}

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = (int)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

var hIndex = function(citations) {
  const 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;
};