### 题目

##### h-index原题

Given an array of citations (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.”

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

##### 本题在原题基础上进一步提问

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

### 朴素解法，$O(n)$

有1篇文章至少有6个引用



#### 代码

class Solution {
public int hIndex(int[] citations) {
for (int i = 0, j = citations.length; i < citations.length; i++, j--) {
if (j <= citations[i]) { return j; }
}
return 0;
}
}


### 二分法，$O(\log_{}{n})$

 1 < 4，所以目标临界点一定在右边
|
0,1,3,5,6
|-----|
缩小范围

 5 > 2，所以目标临界点不可能在右边
|
0,1,3,5,6
|-----|



#### 代码

class Solution {
public int hIndex(int[] citations) {
int len = citations.length;
int lo = 0, hi = len-1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (citations[mid] < (len - mid)) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return len - lo;
}
}