LeetCode 274. H指数

摘要：
题目有点绕，好在一遍A。

题目

给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 $h$ 指数。

h 指数的定义： $h$ 代表“高引用次数”（high citations），一名科研人员的 $h$ 指数是指他（她）的（N 篇论文中）总共有 $h$ 篇论文分别被引用了至少 $h$ 次。且其余的 $N - h$ 篇论文每篇被引用次数 不超过 $h$ 次。

例如：某人的 $h$ 指数是 $20$，这表示他已发表的论文中，每篇被引用了至少 $20$ 次的论文总共有 $20$ 篇。

示例：

输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。

由于研究者有 3 篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，所以她的 h 指数是 3。

提示：如果 $h$ 有多种可能的值，$h$ 指数是其中最大的那个。

计数排序

题目可以抽象成，在所有的论文当中有 $h$ 篇，其中每篇被引用至少 $h$ 次。

那么我们就开一个计数数组，对于数组第 $i$ 项，记录引用次数为 $i$ 的论文有多少篇。
比如对于示例1，计数数组为：
0-1
1-1
2-0
3-1
4-0
5-1
6-1
从数组末尾开始遍历，当引用次数对应的篇数不为零时，对应着有效的一项。
对于每一个有效项，累加总篇数，和当前下标（即引用次数）比较取最小值 $min$ 就表示当前有 $min$ 篇每篇引用至少 $min$ 次。也就是说每一项都会产生一个新的 $h$ 值，比较所有 $h$ 值取最大者即可。

Q: 为什么要从计数数组末尾开始遍历？
A: 只有从末尾开始遍历，对于每个计数数组中的有效项，累加的篇数和对应下标的引用次数取最小才可以表示成：
在当前累加篇数的论文中，每篇引用至少对应下标次数。从数组开头开始遍历没法表示至少。

class Solution {
public:
    int hIndex(vector<int>& ci) {
        int mx = *max_element(ci.begin(), ci.end());
        int n = ci.size();
        vector<int> cnt(mx + 10, 0);
        for (int i = 0; i < n; i++) {
            cnt[ci[i]]++;
        }
        //for (int i = 0; i < mx + 10; ++i) cout << i << "-"  << cnt[i] << endl;
        //return 0;
        int paper_cnt = 0;
        int res = 0;
        for (int i = mx + 9; i >= 0; i--) {
            if (cnt[i]) {
                paper_cnt += cnt[i];
                int tmp = min(paper_cnt, i);
                res = max(res, tmp);
            }
        }
        return res;
    }
};

原题链接： LeetCode 274. H指数