跳到主要内容

H 指数

· 阅读需 8 分钟
Eureka X
Eureka X
Mr.Nobody

力扣面试经典——274题​

💡 参考代码：​

/**
 * 计算研究者的h指数
 * 
 * h指数的定义：研究者至少发表了h篇论文，并且至少有h篇论文被引用次数大于等于h
 * 
 * @param citations 整数数组，citations[i]表示第i篇论文的引用次数
 * @param citationsSize 数组citations的长度，即论文总数
 * @return 返回该研究者的h指数
 * 
 * 算法思路：
 * 1. 使用计数排序的思想，统计每个引用次数的论文数量
 * 2. 从高到低遍历可能的h值，找到满足条件的最大h值
 * 
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 */
int hIndex(int* citations, int citationsSize) {
    // 创建计数数组，大小为 citationsSize + 1
    // count[i] 表示引用次数为i的论文数量
    int* count = (int*)calloc(citationsSize + 1, sizeof(int));
    
    // 统计每个引用次数的论文数量
    // 如果引用次数超过论文总数，则统一计入count[citationsSize]
    for (int i = 0; i < citationsSize; i++) {
        if (citations[i] >= citationsSize) {
            count[citationsSize]++;  // 引用次数≥n的论文都计入最高计数位
        } else {
            count[citations[i]]++;   // 正常计数
        }
    }
    
    // 从后往前累加，计算引用次数大于等于i的论文数量
    // sum表示引用次数≥i的论文总数
    int sum = 0;
    for (int i = citationsSize; i >= 0; i--) {
        sum += count[i];  // 累加引用次数≥i的论文数量
        if (sum >= i) {   // 如果引用次数≥i的论文数量≥i，则h指数为i
            free(count);
            return i;
        }
    }
    
    free(count);
    return 0;  // 如果没有找到有效的h指数，返回0
}

📖 总结：​

点击展开题目总结

🤔 H 指数

1️⃣ 题目核心信息​

🎯 功能描述：根据给定的论文引用次数数组，计算研究者的h指数。h指数是指研究者至少发表了h篇论文，且这h篇论文每篇都被引用至少h次。

📥 输入输出：

  • 输入：int* citations（论文引用次数数组），int citationsSize（论文总数）
  • 输出：返回h指数值

2️⃣ 实现原理​

💡 核心思路：使用计数排序的思想，统计每个引用次数的论文数量，然后从高到低查找满足条件的最大h值。

📋 实现步骤：

  1. 创建大小为citationsSize + 1的计数数组，用于统计每个引用次数的论文数量
  2. 遍历引用数组，将引用次数超过citationsSize的论文统一计入最高计数位
  3. 从后往前遍历计数数组，累加引用次数大于等于当前索引的论文总数
  4. 当累加和大于等于当前索引时，该索引即为最大的h指数

3️⃣ 关键点解析​

原始思路是遍历每个可能的h值并统计满足条件的论文数量，时间复杂度为O(n²)。最优解使用计数排序思想，将时间复杂度优化到O(n)。

🎯 代码技巧​

  • 计数排序优化：利用引用次数的有限范围特性
  • 边界处理：将引用次数超过n的论文统一处理
  • 逆序累加：从最大可能的h值开始查找，确保找到最大值

4️⃣ 使用场景​

✅ 适用情况：​

  • 计算学术评价指标
  • 统计分析场景
  • 需要评估"数量与质量"综合指标的场景

⚠️ 前提条件：​

  • 输入数组不为空
  • 引用次数为非负整数

5️⃣ 复杂度分析​

  • ⏱️ 时间复杂度：O(n)，需要遍历数组两次

  • 💾 空间复杂度：O(n)，需要额外的计数数组

6️⃣ 注意事项​

🚩 边界情况：​

  • 空数组或只有一个元素
  • 所有论文引用次数都为0
  • 所有论文引用次数都很大

💥 易错点：​

  • 混淆h指数的定义，误以为需要恰好h篇论文引用h次
  • 忘记释放动态分配的内存
  • 边界条件处理不当，如h值可能为0的情况

7⃣ 补充说明​

H 指数解释​

假设某研究者发表了 5 篇论文，引用次数分别为：[3, 0, 6, 1, 5]

我们要找最大的 h，使得至少有 h 篇论文被引用了至少 h 次。

尝试几个 h 值：

  • h = 0：0 篇论文引用 ≥ 0 → 成立（但我们要找最大的 h）
  • h = 1：至少 1 篇论文引用 ≥ 1 → 成立（有 4 篇）
  • h = 2：至少 2 篇论文引用 ≥ 2 → 成立（有 3 篇）
  • h = 3：至少 3 篇论文引用 ≥ 3 → 成立（有 3 篇）
  • h = 4：至少 4 篇论文引用 ≥ 4 → 不成立（只有 2 篇）
  • h = 5：至少 5 篇论文引用 ≥ 5 → 不成立（只有 2 篇）

所以 h 指数是 3。

h指数计算示例详解​

例子：citations = [3, 0, 6, 1, 5]

论文引用次数数组为 [3, 0, 6, 1, 5]，共5篇论文。

第一步：初始化计数数组​

int* count = (int*)calloc(citationsSize + 1, sizeof(int));

创建一个长度为 5 + 1 = 6 的数组 count，所有元素初始为 0：

count = [0, 0, 0, 0, 0, 0]
索引:    0  1  2  3  4  5

calloc与malloc的区别

  • malloc: 只分配内存，不初始化内容（内存中可能包含随机数据）
  • calloc: 分配内存后会将所有字节初始化为0

calloc函数原型：

void* calloc(size_t num, size_t size);

第二步：统计每个引用次数的论文数量​

for (int i = 0; i < citationsSize; i++) {
    if (citations[i] >= citationsSize) {
        count[citationsSize]++;
    } else {
        count[citations[i]]++;
    }
}

逐个处理每篇论文的引用次数：

  • citations[0] = 3 → count[3]++ → count = [0, 0, 0, 1, 0, 0]
  • citations[1] = 0 → count[0]++ → count = [1, 0, 0, 1, 0, 0]
  • citations[2] = 6 → 6 >= 5 → count[5]++ → count = [1, 0, 0, 1, 0, 1]
  • citations[3] = 1 → count[1]++ → count = [1, 1, 0, 1, 0, 1]
  • citations[4] = 5 → count[5]++ → count = [1, 1, 0, 1, 0, 2] 最终 count 数组为：
count = [1, 1, 0, 1, 0, 2]
索引:    0  1  2  3  4  5

这表示：

  • 引用次数为 0 的论文有 1 篇
  • 引用次数为 1 的论文有 1 篇
  • 引用次数为 2 的论文有 0 篇
  • 引用次数为 3 的论文有 1 篇
  • 引用次数为 4 的论文有 0 篇
  • 引用次数 ≥ 5 的论文有 2 篇

第三步：从后往前累加，找最大的 h​

int sum = 0;
for (int i = citationsSize; i >= 0; i--) {
    sum += count[i];
    if (sum >= i) {
        free(count);
        return i;
    }
}

从 i = 5 开始往下检查：

  • i = 5:

sum += count[5] → sum = 0 + 2 = 2

  • 判断 sum >= i → 2 >= 5？ ❌ 不成立

  • i = 4:

  • sum += count[4] → sum = 2 + 0 = 2

  • 判断 sum >= i → 2 >= 4？ ❌ 不成立

  • i = 3:

  • sum += count[3] → sum = 2 + 1 = 3

  • 判断 sum >= i → 3 >= 3？ ✅ 成立！返回 3 结果 函数返回 3，这就是该研究者的 h 指数。

验证一下 引用次数数组：[3, 0, 6, 1, 5]

我们检查是否有至少 3 篇论文引用次数 ≥ 3：

  • 论文1: 3 ≥ 3 ✅
  • 论文2: 0 ≥ 3 ❌
  • 论文3: 6 ≥ 3 ✅
  • 论文4: 1 ≥ 3 ❌
  • 论文5: 5 ≥ 3 ✅

有 3 篇论文满足条件，所以 h 指数确实是 3。

最初思路​

惭愧，这题我最初没做出来，题目理解都是错的，上面的最优解自然是AI给，下面这个我最初的思路，经过AI完善逻辑后的代码：

int hIndex(int* citations, int citationsSize) {
    int maxH = 0;
    
    // 尝试每个可能的h值（从0到citationsSize）
    for (int h = 0; h <= citationsSize; h++) {
        int count = 0;
        
        // 计算引用次数>=h的论文数量
        for (int i = 0; i < citationsSize; i++) {
            if (citations[i] >= h) {
                count++;
            }
        }
        
        // 如果引用次数>=h的论文数量>=h，则h是一个有效值
        if (count >= h) {
            if (h > maxH) {
                maxH = h;
            }
        }
    }
    
    return maxH;
}

对H指数计算算法的理解​

算法核心思路

  • H指数定义：有h篇论文至少被引用h次，其余论文引用次数不超过h次

  • 关键观察：H指数的取值范围是[0, n]，其中n是论文总数

算法步骤解析

1.构建计数数组

  • 创建长度为 n+1 的数组 count

  • count[i] 表示引用次数恰好为 i 的论文数量

  • 对于引用次数超过 n 的论文，统一计入 count[n]

2.统计引用次数分布

  • 遍历 citations 数组

  • 对每个引用次数进行计数统计

3.计算H指数

  • 从后向前遍历 count 数组

  • 累计引用次数≥当前下标的文章数量

  • 当累计数量≥当前下标时，该下标即为H指数

加载评论中...