给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 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
提示：
n == citations.length1 <= n <= 50000 <= citations[i] <= 1000
最容易理解的——排序后遍历
先对原数组进行排序，我们要找最大值的h就是要满足大于等于h的数大于等于h，所以排序之后我们可以知道大于每个数的数有多少，进行查找最大值即可
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.begin(),citations.end());
int n=citations.size();
for(int i=0;i<n;i++) {
if(citations[i]>=n-i) return n-i;
}
return 0;
}
};
稍微优化——遍历改成二分搜索
class Solution {
public:
int hIndex(vector<int>& citations) {
size_t n = citations.size();
sort(citations.begin(), citations.end());
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (citations[mid] >= n - mid) high = mid - 1;
else low = mid + 1;
}
return n - low;
}
};
差分数组解法（计数排序）
差分数组讲解可参考【算法】排序算法之计数排序 - 知乎 (zhihu.com)
这里因为h<=n,所以大于n的数按n算就行，cnt数组大小n+1
class Solution {
public:
int hIndex(vector<int>& citations) {
//计数排序
int n=citations.size();
vector<int> counter(n+1) ;//因为h<=n,所以>n的值都存入counter[n]
for(int i=0;i<n;i++) {
if(citations[i]>=n) counter[n]++;
else counter[citations[i]]++;
}
int cnt=0;//cnt记录大于i （即citations[某个值]）的值个数
for(int i=n;i>=0;i--) {//从大到小遍历
cnt+=counter[i];
if(cnt>=i) {
//如果大于i的数个数大于i，那么h=i
return i;
}
}
return 0;
}
};class Solution {
public:
int hIndex(vector<int>& citations) {
//计数排序
int n=citations.size();
vector<int> counter(n+1) ;//因为h<=n,所以>n的值都存入counter[n]
for(int i=0;i<n;i++) {
if(citations[i]>=n) counter[n]++;
else counter[citations[i]]++;
}
int cnt=0;//cnt记录大于i （即citations[某个值]）的值个数
for(int i=n;i>=0;i--) {//从大到小遍历
cnt+=counter[i];
if(cnt>=i) {
//如果大于i的数个数大于i，那么h=i
return i;
}
}
return 0;
}
};