2019-11-22 14:10:19
Google kickstart 2019 h round 的A题是h-index，leetcode上也有两条相关问题，本次对h-index问题做一个汇总。
- 274. H-Index
问题描述：
问题求解：
h-index描述：至少有h篇论文的引用数量大于等于h。
解法一：排序
我们想象一个直方图，其中 xx 轴表示文章，yy 轴表示每篇文章的引用次数。如果将这些文章按照引用次数降序排序并在直方图上进行表示，那么直方图上的最大的正方形的边长 hh 就是我们所要求的 hh。
public int hIndex(int[] citations) {
int n = citations.length;
Arrays.sort(citations);
int res = 0;
while (res < n && citations[n - 1 - res] >= res + 1) res += 1;
return res;
}
解法二：计数
不难发现，如果引用数量大于发表的论文数目，将之降到论文数是不会影响最后的结果的。这样，我们就可以通过计数排序将整个算法的时间复杂度降到O(n)。
public int hIndex(int[] citations) {
int n = citations.length;
int[] nums = new int[n + 1];
for (int cit : citations) {
nums[Math.min(cit, n)]++;
}
int res = 0;
for (int i = n - 1; i >= 0; i--) {
nums[i] = nums[i] + nums[i + 1];
}
for (int i = 0; i <= n; i++) {
if (i <= nums[i]) res = Math.max(res, i);
}
return res;
}
- 275. H-Index II
问题描述：
问题求解：
本题是一个follow up问题，由于已经进行了排序，所以可以使用O(n)遍历一遍就可以得到结果。当然由于lc的测试数据不够强大，单纯的O(n)的解法也可以过。
但是其实本质上来说，本题还是要求去找一个对数时间的算法。
public int hIndex(int[] citations) {
int n = citations.length;
if (citations.length == 0 || citations[n - 1] < 1) return 0;
// 寻找一个citations[idx] >= n - 1 - idx 最大的idx
// [l, r)
int l = 0;
int r = citations.length;
while (r - l > 1) {
int mid = l + (r - l) / 2;
if (citations[n - 1 - mid] >= mid + 1) l = mid;
else r = mid;
}
return l + 1;
}