LeetCode 274：H 指數計算

題目：給定引用次數數組 citations，計算 H 指數。定義：至少有 h 篇論文引用 ≥ h 次，其餘論文引用 ≤ h 次。取最大滿足條件的 h。

解法一：排序法 O(n log n)

降序排序 citations。遍歷索引 i (0-based)，若 citations[i] >= i+1 則 h = i+1 為候選。最後一個滿足條件的即為答案。

解法二：計數排序 O(n) 時間 O(n) 空間（最優）

H 指數最大不超過論文總數 n。建立長度 n+1 計數數組 cnt：
cnt[i] 存引用數為 i 的論文數 (i=n 存 ≥ n 的)。
從後向前累加 cnt[i] += cnt[i+1]，得到引用數 ≥ i 的論文總數。
第一個滿足 cnt[i] >= i 的 i 即為 H 指數。

public int hIndex(int[] citations) {
    int n = citations.length;
    int[] cnt = new int[n + 1];
    for (int c : citations)
        cnt[Math.min(c, n)]++;
    for (int i = n; i >= 0; --i) {
        if (i < n) cnt[i] += cnt[i + 1];
        if (cnt[i] >= i) return i;
    }
    return 0;
}

關鍵點

• 引用數 > n 的論文歸入 cnt[n]，因 H 指數上界是 n。
• 逆序累加把「等於 i」轉為「≥ i」。
• 從大到小遍歷保證找到最大 h。

總結

計數排序利用 H 指數上界特性將時間複雜度降至線性，是面試加分項。排序法代碼更短，工程實踐足夠。