H指数
一 问题描述
给定一个整数数组 citations ，其中 citations[i] 代表研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
h 代表“高引用次数“，一名科研人员的 h 指数是指他（她）至少发表了 h 篇论文，且至少有 h 篇论文的被引用次数大于等于 h 。如果 h 有多种可能值，那 h 指数是其中最大的那个。
二 解决方法
1 暴力法
分析
因为 h 指数一定小于等于论文数，因此只要穷举所有的论文数，就一定能找到 h 指数。
具体做法如下：使用两层循环，第一层循环尝试所有可能的引用数（最大为论文数）作为 h 指数的候选值，第二层循环遍历数组，记录引用次数大于 h 的元素个数即论文数，找到最大满足「论文数大于引用数」的值，即为 h 值。
代码
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size(); // 转储数组大小
int refCnt = n; // 初始化最高引用数为数组大小（论文篇数）
while (refCnt--) { // 尝试所有可能的引用次数（从高到低）
int paperCnt = 0; // 初始化高引用论文数为0
for (int j = 0; j < n; ++j) { // 遍历数组
if (citations[j] >= refCnt) { // 记录引用次数高于指定次数的论文
++paperCnt;
}
}
if (paperCnt >= refCnt) { // 如果首次找到（即最高）满足条件引用次数，跳出循环
break;
}
}
return refCnt; // 返回引用次数
}
};复杂度
-
时间复杂度：
O(n^2)，遍历长度为n的数组嵌套遍历两次。 -
空间复杂度：
O(1)，只使用常数个变量。
2 排序
分析
h 指数代表“高引用次数”，不妨将代表论文引用次数的数组 citations 排序。此时，只要找到一个位置的引用次数，大于其之后的元素个数（论文篇数），该引用次数即为 h 指数。
因为需要计算数组中某一位置元素后的元素个数，反向遍历比较合适，具体做法如下：初始化一变量为0，用于存储元素个数，反向遍历数组，在每次访问完一元素时，累加该变量。
代码
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.begin(), citations.end()); // 排序
int n = citations.size(); // 转储数组打下
int h = 0; // 初始化h指数为0
for (int i = n - 1; i >= 0; --i) { // 反向遍历排序后的数组
if (citations[i] > h) { // 如果引用次数大于h指数
++h; // h指数累加
}
}
return h; // 返回h指数
}
};复杂度
-
时间复杂度：
O(nlogn)，即排序长度为n数组的时间复杂度。 -
空间复杂度：
O(n)，即排序长度为n数组的空间复杂度。
3 计数排序
计数排序：将原数组以新的计数数组方式存储，以达到排序效果。其中计数数组是：数组下标为元素值，数组元素为原数组元素出现的次数。因为数组下标（此时还表示原数组元素）本就是排序好的，因此也可以看作是一种排序。新的数组大小也就是原数组中最大的值，因此计数排序一般用于整数数组，且最大值已知。
分析
计数排序的关键在于找到原数组的最大值，以方便构建计数数组。由题意知： h 指数不会大于研究者的论文篇数 n ，因此所有引用次数大于 n 的论文都可以存储在第 n+1 个位置。也就是说计数数组大小为 n+1 。
当获得按计数排序的数组后，反向遍历，累加论文篇数（数组元素），找到首次论文篇数大于等于引用数（数组下标）的下标位置，此时的下标值即为 h 指数。
代码
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size(); // 转储数组大小
int cnt = 0; // 初始化计数和为0
vector<int> counter(n + 1, 0); // 初始化计数数组为{0}，用于存储按计数排序后的数组
for (int i = 0; i < n; ++i) { // 遍历数组，构建计数数组
if (citations.at(i) > n) { // 引用次数大于n，按照次数为n记录
++counter[n]; //
} else {
++counter[citations.at(i)]; // 否则按照实际次数记录
}
}
for (int i = n; i >= 0; --i) { // 反向遍历计数数组
cnt += counter.at(i); // 累加当前引用次数下的论文篇数
if (cnt >= i) { // 论文篇数大于等于当前引用次数
return i; // 找到h指数，返回结果
}
}
return 0; // 为找到h指数，返回0
}
};复杂度
-
时间复杂度：
O(n)，遍历数组长度为n的citations数组一次，遍历数组长度为n+1的counter数组一次。 -
空间复杂度：
O(n)，构建长度为n+1的数组counter。
三 总结
- 当排序能解决问题，且数组元素为整数值时，不妨考虑计数排序。