一. 简介
前面一篇文章针对力扣网274题（H指数）使用排序，遍历数组方法进行处理的，文章如下：
时间复杂度为 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篇文章被引用次数>=i
if(total >= i) {
return i;
}
}
return 0;
}可以看出，计数排序这种解法的时间复杂度为 O(n)。