leetcode274.H指数

题目描述

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

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

题目解法

解法一：暴力

从h=0开始，每次h加1，然后统计有多少篇论文的引用次数 ≥ 当前尝试的h。当统计到的论文数cnt首次小于h时，返回h-1。

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int cnt = 0, h = -1; // 初始化 cnt 和 h
        while (h <= cnt) { // 当统计到的篇数 cnt 大于等于当前尝试的 h 值时继续循环
            cnt = 0; // 重置计数器
            h++; // 尝试下一个更大的 h 值
            for (int i = 0; i < n; i++) { // 遍历所有论文
                if (citations[i] >= h) { // 如果论文引用次数 >= 当前尝试的 h
                    cnt++; // 计数加1
                }
            }
        }
        return h - 1; // 循环退出时，说明 h 值过大，返回 h-1
    }
}

示例​​：以 citations = [3,0,6,1,5]为例：

• 尝试 h=0：统计 cnt（引用次数≥0的论文数）= 5。∵ 5 >= 0 ∴ 继续。
• 尝试 h=1：cnt（引用次数≥1的论文数）= 4。∵ 4 >= 1 ∴ 继续。
• 尝试 h=2：cnt（引用次数≥2的论文数）= 3。∵ 3 >= 2 ∴ 继续。
• 尝试 h=3：cnt（引用次数≥3的论文数）= 3。∵ 3 >= 3 ∴ 继续。
• 尝试 h=4：cnt（引用次数≥4的论文数）= 2。∵ 2 < 4 ∴ 退出循环。
• 返回 h-1 = 3。 结果正确。

时间复杂度为，最坏情况下，如果所有的论文引用次数都很高，时间复杂度为。

解法二：计数排序

计数排序的核心思想是统计每个整数出现的次数，然后根据计数信息计算出每个元素在有序序列中的最终位置。他的流程可以精炼为以下几个关键步骤：

1. ​找出最大值和最小值​​：遍历数组，确定待排序数组中的最大值 max和最小值 min，从而计算出数据的范围 range = max - min + 1。
2. 创建并填充计数数组​​：创建一个长度为 range的计数数组 count，并初始化为0。再次遍历原数组，对于每个元素 num，在 count[num - min]位置上的计数增加1（这样就将数据映射到了计数数组的索引上）。
3. 计算前缀和​​：对计数数组进行变形，从第一个元素开始，将每个索引的值加上前一个索引的值。变形后的 count[i]表示​​小于等于 i + min这个值的元素总个数​​（即元素在有序数组中的尾索引位置）。这一步对于实现​​稳定排序​​很重要。
4. 重构有序数组​​：
   • 创建一个与原数组等长的输出数组 output。从后往前​​遍历原数组（为了保持排序的稳定性）。
   • 对于当前元素 num，找到其在计数数组中对应的索引 index = num - min。此时 count[index]  - 1就是该元素在输出数组中​​应该放置的位置​​。
   • 将 num放入 output[count[index] - 1]，并将 count[index]减1（为下一个相同的元素腾位置）

假设有数组 arr = [4, 2, 2, 8, 3, 3, 1]：

1. min = 1, max = 8, range = 8 - 1 + 1 = 8。
2. 创建计数数组count，长度为8，统计后：

   1. count[1-1=0] = 1(数字1出现1次)

   2. count[2-1=1] = 2(数字2出现2次)

   3. count[3-1=2] = 2(数字3出现2次)

   4. count[4-1=3] = 1(数字4出现1次)

   5. count[8-1=7] = 1(数字8出现1次)

3. 对 count求累加和得到 [1, 3, 5, 6, 6, 6, 6, 7]。这意味着：

   1. count[0]=1：≤1的元素有1个

   2. count[1]=3：≤2的元素有3个

   3. count[2]=5：≤3的元素有5个

   4. count[7]=7：≤8的元素有7个

4. 从后往前遍历 arr（稳定排序关键）：

   1. 最后一个元素是1，index = 1-1=0, count[0]=1-> 位置 1-1=0，output[0]=1，count[0]减为0。

   2. 接着是3，index=3-1=2, count[2]=5-> 位置 5-1=4，output[4]=3，count[2]减为4。

   3. 依此类推 ...

这里，我们创建一个长度为 n+1（n为论文总数）的数组 count，初始值全为0。count[i]的含义是：​​恰好被引用 i次的论文有多少篇​​。

接下来，我们根据计数排序的步骤，​遍历给定的论文引用次数数组 citations，填充 count数组。

逆向累加寻找h：从 i = n开始​​逆向遍历​​（从大到小）count数组，同时用一个变量（通常叫 total或 sum）​​累加​​当前引用次数及以上（≥i）的论文总篇数。​​一旦发现 total >= i​​，就意味着找到了满足“至少有 i篇论文被引用了至少 i次”的条件，此时的 i就是最大的 H 指数，直接返回即可。

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] count = new int[n + 1];

        for (int c : citations) {
            if (c >= n) {
                count[n]++;
            } else {
                count[c]++;
            }
        }

        int cnt = 0;
        for (int i = n; i >= 0; i--) {
            cnt += count[i];
            if (cnt >= i) {
                return i;
            }
        }
        return 0;
    }
}