274. H 指数

✨核心逻辑

本题要求寻找最大的 h，使得有至少 h 篇论文的引用次数 ≥ h。由于 h 的范围在 [0, n] 之间，这里提供三种解题思路：

排序法：将引用次数升序排序。从前往后遍历，对于索引 i，剩余未遍历的文章数量 n - i 即为当前可满足的 h。如果 citations[i] >= n - i，说明找到了第一个满足条件的最大 h，直接返回。

🔥代码实现（含详细变量注释）

package array_string;

import java.util.Arrays;

public class hIndex_274 {

    // 方法 1：排序法（直观且简单）
    public int hIndex(int[] citations) {
        // 对引用次数数组进行从小到大的排序
        Arrays.sort(citations);
        // n：记录论文的总篇数
        int n = citations.length;
        
        // i：遍历数组的指针，表示当前已经看过了前 i 篇引用次数较少的论文
        for (int i = 0; i < citations.length; i++) {
            // h：计算在排序后，从当前位置到数组末尾剩余的文章数量
            // 这些剩余的论文，其引用次数一定都大于等于 citations[i]
            int h = n - i;
            
            // 关键判断：如果当前这篇论文的引用次数 citations[i] 大于等于剩余的篇数 h
            // 说明至少有 h 篇论文的引用次数 >= h，直接返回当前最大的 h
            if (citations[i] >= h) {
                return h;
            }
        }
        // 如果没有找到满足条件的 h，则返回 0
        return 0;
    }

计数排序（桶排序）：核心思想是利用“引用次数大于等于 n”的这一特性，将所有论文放入 n + 1 个桶中。从后往前累加桶内论文的数量，只要某时刻累加的论文数 count >= j（桶下标），即说明存在至少 j 篇论文引用次数 ≥ j，直接返回 j。

    // 方法 2：计数排序 / 桶排序（时间复杂度 O(N)）
    public int hIndex1(int[] citations) {
        // n：记录数组的长度
        int n = citations.length;
        // buckets：创建大小为 n + 1 的桶数组。索引 i 表示引用次数为 i 的论文数量
        // 引用次数超过 n 的论文统一放到最后一个桶（下标为 n）中
        int[] buckets = new int[n + 1];
        
        // 遍历每篇论文的引用次数，装入对应的桶中
        for (int i : citations) {
            if (i >= n) {
                // 如果引用次数 >= 论文总数 n，放入下标为 n 的桶
                buckets[n]++;
            } else {
                // 否则放入对应引用次数下标的桶中
                buckets[i]++;
            }
        }
        
        // count：记录从后往前累加的论文总数量
        int count = 0;
        // j：从后往前遍历桶的下标（从可能的 H 指数最大值 n 开始向下寻找）
        for (int j = n; j >= 0; j--) {
            // 累加当前桶的论文数量到 total 中
            count += buckets[j];
            
            // 条件判断：如果当前累加的论文总数 count >= 当前桶的下标 j
            // 说明至少有 j 篇论文的引用次数 >= j，此时 j 就是最大的 H 指数，直接返回
            if (j <= count) {
                return j;
            }
        }
        return 0;
    }

二分查找法：h 本身满足单调性，可以使用二分查找。猜测一个 mid，借助 Helper 函数检查是否有至少 mid 篇论文引用次数 ≥ mid。如果满足，说明还有提升空间（left = mid），否则说明猜测过大（right = mid - 1），最终找出最大有效 h。


    // 方法 3：二分查找法
    public int hIndex2(int[] citations) {
        int n = citations.length;
        // left：二分查找的左边界（最小可能的 h 为 0）
        // right：二分查找的右边界（最大可能的 h 为 n）
        int left = 0, right = n;
        
        // 在 [0, n] 的区间内二分查找满足条件的最大 h
        while (left < right) {
            // mid：利用向上取整的计算方式，避免区间只剩两个元素时出现死循环
            int mid = left + (right - left + 1) / 2;
            
            // Helper 函数判断：是否有至少 mid 篇论文的引用次数 >= mid
            if (Helper(citations, mid)) {
                // 如果满足条件，说明 h 还可以更大，收缩左边界
                left = mid;
            } else {
                // 如果不满足条件，说明 mid 猜大了，收缩右边界
                right = mid - 1;
            }
        }
        // 最终的 left 就是最大满足条件的 H 指数
        return left;
    }
    
    // 二分查找的辅助函数：用于验证猜测的 mid 是否合法
    public boolean Helper(int[] citations, int mid) {
        // count：统计引用次数 >= mid 的论文数量
        int count = 0;
        // 遍历整个引用数组
        for (int num : citations) {
            if (num >= mid) {
                count++;
            }
        }
        // 如果满足条件的论文数量 count >= mid，说明猜测合法，返回 true
        return count >= mid;
    }
}