642 字
3 分钟
274. H 指数
274. H 指数
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。
示例
示例 1：
输入：citations = [3,0,6,3,1,5]输出：3解释：给定数组表示研究者总共有 6 篇论文，每篇论文相应的被引用了 3, 0, 6, 3, 1, 5 次。 由于研究者有 4 篇论文每篇 至少 被引用了 3 次，其余2篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。示例 2：
输入：citations = [1,3,1]输出：1提示：
n == citations.length1 <= n <= 50000 <= citations[i] <= 1000思路
- 首先想到的是统计每个引用次数的论文数量。
- 问题来了，已知次数之后，如何比较到底有多少篇论文满足 h 指数的定义。如果顺序地从小到达进行遍历，那么假设要统计大于等于 i 次引用的论文数量，就需要遍历所有的引用次数数组。这样明显效率不高。
- 于是想到论文的总数是固定的，可以从小到大进行遍历，每次都删除当前引用次数的论文数量。这样就可以统计大于等于 i 次引用的论文数量，逐渐增加引用次数，不断逼近最大的H指数。
- 当论文数量 小于等于 引用次数时，论文数量首次低于引用次数，不满足H指数的定义。
- 相反，这说明在这之前，如果加上当前引用次数的论文数量，是满足H指数的要求的，此时引用次数最大，返回引用次数。
- 时间复杂度和空间复杂度都是。
代码
class Solution {public: int hIndex(vector<int>& citations) { // 特定引用次数的论文的数量。 vector<int> citation_count(1001, 0); for(int i = 0; i < citations.size(); i++){ citation_count[citations[i]]++; } // 大于i次引用的论文数量 int ans = citations.size(); for(int i = 0; i < citations.size(); i++){ // 逐渐减少，逼近最大H指数 ans -= citation_count[i]; // 当论文数量 小于等于 引用次数时，返回引用次数。 if(ans <= i){ return i; } } return ans; }};