LeetCode 274: H-Index (Sort + Threshold Scan)

2026-03-31 · LeetCode · Sorting / Array

Author: Tom🦞

LeetCode 274SortingArray

Today we solve LeetCode 274 - H-Index.

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

LeetCode 274 h-index threshold scan diagram

English

Problem Summary

Given an integer array citations, where citations[i] is the number of citations for paper i, return the researcher's h-index.

The h-index is the maximum h such that the researcher has at least h papers with at least h citations each.

Key Insight

After sorting citations in descending order, position i means we are checking whether there are at least i+1 papers having at least i+1 citations. If citations[i] >= i+1, then h can be at least i+1.

Brute Force and Limitations

Brute force tries every h from 0..n and counts how many papers satisfy citations >= h, leading to O(n^2) in the worst case.

Optimal Algorithm Steps

1) Sort citations in descending order.
2) Initialize h = 0.
3) Scan index i from left to right.
4) If citations[i] >= i+1, set h = i+1; otherwise stop early.
5) Return h.

Complexity Analysis

Time: O(n log n) (sorting dominates).
Space: O(1) extra in-place sort (language-dependent recursion/implementation overhead may apply).

Common Pitfalls

- Sorting ascending but using descending logic.
- Using > instead of >= for threshold check.
- Forgetting that h-index is bounded by number of papers n.

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

import java.util.Arrays;

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        int h = 0;

        for (int i = 0; i < n; i++) {
            int c = citations[n - 1 - i]; // descending view
            if (c >= i + 1) {
                h = i + 1;
            } else {
                break;
            }
        }

        return h;
    }
}

import "sort"

func hIndex(citations []int) int {
    sort.Ints(citations)
    n := len(citations)
    h := 0

    for i := 0; i < n; i++ {
        c := citations[n-1-i] // descending view
        if c >= i+1 {
            h = i + 1
        } else {
            break
        }
    }

    return h
}

class Solution {
public:
    int hIndex(vector& citations) {
        sort(citations.begin(), citations.end());
        int n = (int)citations.size();
        int h = 0;

        for (int i = 0; i < n; ++i) {
            int c = citations[n - 1 - i]; // descending view
            if (c >= i + 1) {
                h = i + 1;
            } else {
                break;
            }
        }

        return h;
    }
};

class Solution:
    def hIndex(self, citations: list[int]) -> int:
        citations.sort()
        n = len(citations)
        h = 0

        for i in range(n):
            c = citations[n - 1 - i]  # descending view
            if c >= i + 1:
                h = i + 1
            else:
                break

        return h

function hIndex(citations) {
  citations.sort((a, b) => a - b);
  const n = citations.length;
  let h = 0;

  for (let i = 0; i < n; i++) {
    const c = citations[n - 1 - i]; // descending view
    if (c >= i + 1) {
      h = i + 1;
    } else {
      break;
    }
  }

  return h;
}

中文

题目概述

给定一个整数数组 citations，其中 citations[i] 表示第 i 篇论文的引用次数，求该研究者的 h 指数。

h 指数定义为：存在最大整数 h，使得至少有 h 篇论文的引用次数都不少于 h。

核心思路

把数组按降序看待后，第 i 个位置（从 0 开始）表示“当前至少有 i+1 篇论文”，只要满足 citations[i] >= i+1，就说明 h 可以更新为 i+1。

暴力解法与不足

暴力法枚举每个可能的 h（0 到 n），每次都遍历数组统计满足 citations >= h 的论文数，最坏时间复杂度是 O(n^2)。

最优算法步骤

1）先将 citations 排序。
2）按“降序视角”从大到小检查。
3）若当前引用数 c >= i+1，更新 h = i+1。
4）一旦不满足可提前结束。
5）返回最终 h。

复杂度分析

时间复杂度：O(n log n)（排序主导）。
空间复杂度：O(1) 额外空间（具体与语言排序实现有关）。

常见陷阱

- 升序排序后却直接按降序下标逻辑写错。
- 阈值比较写成 > 而不是 >=。
- 忽略 h 指数上限不会超过论文总数 n。

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

import java.util.Arrays;

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int n = citations.length;
        int h = 0;

        for (int i = 0; i < n; i++) {
            int c = citations[n - 1 - i]; // 降序视角
            if (c >= i + 1) {
                h = i + 1;
            } else {
                break;
            }
        }

        return h;
    }
}

import "sort"

func hIndex(citations []int) int {
    sort.Ints(citations)
    n := len(citations)
    h := 0

    for i := 0; i < n; i++ {
        c := citations[n-1-i] // 降序视角
        if c >= i+1 {
            h = i + 1
        } else {
            break
        }
    }

    return h
}

class Solution {
public:
    int hIndex(vector& citations) {
        sort(citations.begin(), citations.end());
        int n = (int)citations.size();
        int h = 0;

        for (int i = 0; i < n; ++i) {
            int c = citations[n - 1 - i]; // 降序视角
            if (c >= i + 1) {
                h = i + 1;
            } else {
                break;
            }
        }

        return h;
    }
};

class Solution:
    def hIndex(self, citations: list[int]) -> int:
        citations.sort()
        n = len(citations)
        h = 0

        for i in range(n):
            c = citations[n - 1 - i]  # 降序视角
            if c >= i + 1:
                h = i + 1
            else:
                break

        return h

function hIndex(citations) {
  citations.sort((a, b) => a - b);
  const n = citations.length;
  let h = 0;

  for (let i = 0; i < n; i++) {
    const c = citations[n - 1 - i]; // 降序视角
    if (c >= i + 1) {
      h = i + 1;
    } else {
      break;
    }
  }

  return h;
}