力扣网编程274题：H指数之计数排序（中等）

一. 简介

前面一篇文章针对力扣网274题（H指数）使用排序，遍历数组方法进行处理的，文章如下：

力扣网编程274题：H指数之普通解法（中等）-CSDN博客

时间复杂度为 O(n log(n))，比较高。本文使用计数排序方法进行处理。

二. 力扣网编程274题：H指数之计数排序（中等）

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

示例 1：
输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

示例 2：
输入：citations = [1,3,1]
输出：1

题目分析：

这道题要求计算研究者的H指数，即找到一个最大的h，使有 h 篇文章的引用次数 >= h次。

这里使用计数排序的方法，具体策略是统计引用次数的分布。

解题思路二：（计数排序的思想）

1.  创建计数数组count，创建一个长度为 n+1的计数数组：

i < n时，count[i] 表示恰好被引用 i 的论文数量；

i >= n时，count[i] 表示引用次数 >=n 的论文数量；

2. 统计论文被引用次数的分布：

论文引用次数 < n 时, 使用counter[citations[i]]记录，表示引用次数为 citations[i] 的论文数量。
如果某篇论文的引用次数 >= n（总论文数），我们直接将其归类到 counter[n]（因为 H指数最大不超过 n）。

3. 从高到低累加论文数，寻找最大的h：

    从 n（最大可能的 H指数）开始向下遍历。
    total += counter[i]进行累加（被引用次数从高到低），表示引用次数 >= i 的论文总数。
    如果 total >= i，说明至少有 i 篇论文的引用次数 >= i，直接返回 i（即 H指数）。

C语言实现如下：

//计数排序
int hIndex(int* citations, int citationsSize) {int i;//统计引用次数>=i的文章的数量int total = 0;//统计被引用次数的文章数量//因为h<=citationsSize，所以，被引用次数>=citationsSize的文章数目//被统计在count[citationsSize]int count[citationsSize+1];memset(count, 0, sizeof(count));//统计被引用x次的文章的数量(x为0,1,2...,citationsSize-1, >=citationsSize)for(i = 0; i < citationsSize; i++) {if(citations[i] < citationsSize) {count[citations[i]]++;}else { //v被引用次数>=citationsSize的文章count[citationsSize]++;}}for(i = citationsSize; i >=0; i--){total += count[i];//total: 表示被引用次数>=i的文章数量//total >= i: 表示有i篇文章被引用次数>=iif(total >= i) {return i;}}return 0;
}

可以看出，计数排序这种解法的时间复杂度为 O(n)。