Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.
According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”
Example:
Input:citations = [0,1,3,5,6]Output: 3 Explanation:[0,1,3,5,6]means the researcher has5papers in total and each of them had received 0, 1, 3, 5, 6citations respectively. Since the researcher has3papers with at least3citations each and the remaining two with no more than3citations each, her h-index is3.
Note:
If there are several possible values for h, the maximum one is taken as the h-index.
Follow up:
- This is a follow up problem to H-Index, where
citationsis now guaranteed to be sorted in ascending order. - Could you solve it in logarithmic time complexity?
是LeetCode H-Index的延伸，如果citations是按升序排列的，怎样把算法优化到O(logn)。看到O(logn)，马上想到二分查找。 首先左右边界是0和n-1，判断中点的citations[m]和n-m，如果正好相等，则说明正好有n-m篇大于等于n-m引用的文章，所以H-index为n-m。如果citations[m]>n-m，说明引用很大，h-index还能往上涨，所以中心点需要左移，即r=m-1。反之则中心点右移l=m+1。
代码如下：
class Solution {
public:
int hIndex(vector<int>& citations)
{
int l = 0, n = citations.size(), r = n – 1;
while (l <= r) {
int m = l + (r – l) / 2;
if (n – m == citations[m])
return n – m;
else if (citations[m] > n – m)
r = m – 1;
else
l = m + 1;
}
return n – l;
}
};本代码提交AC，用时9MS。
我一开始的代码是，如果citations[m]<n-m，中心点确实右移了，即l=m+1。但是当citations[m]>n-m时，我没想到用r=m-1来左移中心点，误以为r一直都是n-1是固定的，所以这个时候使用了一个while循环来线性查找正确的m，理论上性能要比上面的纯二分差。
代码如下：
class Solution {
public:
int hIndex(vector<int>& citations)
{
int l = 0, r = citations.size() – 1, n = citations.size();
if (n == 0)
return 0;
if (citations[0] >= n)
return n;
while (l < r) {
int m = l + (r – l) / 2;
if (n – m > citations[m])
l = m + 1;
else {
while (m > 0 && n – m <= citations[m])
–m;
return n – m – 1;
}
}
if (citations[r] >= 1)
return 1;
else
return 0;
}
};本代码提交AC，用时也是9MS。
二刷。更好理解的二分，因为是从小到大排序的，选定中点m后，中点及其右边共有n-m篇paper，如果paper数和citation相等，正好；如果citations[m]更大，则还可以增加paper数，所以r=m-1区间左移，右边合法的paper区间增大。因为如果合法的话，区间会一直左移，r会一直m-1，直到不满足要求，退出while循环，所以最后一个合法的下标r+1，则右边的paper数为n-(r+1)。
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
int l = 0, r = n - 1;
while (l <= r) {
int m = l + (r - l) / 2;
int papers = n - m;
if (citations[m] == papers) {
return papers;
}
else if (citations[m] >= papers) {
r = m - 1;
}
else {
l = m + 1;
}
}
return n - (r + 1);
}
};
