Follow up for 第274題[H-Index] http://www.reibang.com/p/571bf9481ede
What if the citations array is sorted in ascending order? Could you optimize your algorithm?
Solution：Binary Search
思路： 二分長(zhǎng)度查找mid處的citations[mid]是否已經(jīng)可以滿足條件(citations大于它的(它的右邊)已經(jīng)有citations[mid]個(gè)paper數(shù)量[通過(guò)長(zhǎng)度判斷])笆豁，滿足的話繼續(xù)往左邊part找蜀铲，不滿足往右邊part找
［0 2 3 5 6 8］
pattern: 滿足 滿足 滿足 不滿足 不滿足 不滿足
Time Complexity: O(logN) Space Complexity: O(1)
Solution Code：
class Solution {
public int hIndex(int[] citations) {
int length = citations.length;
if(length == 0) return 0;
if(length == 1) return citations[0] >= 1 ? 1 : 0;
int start = 0, end = length - 1;
while(start <= end) {
int mid = start + (end - start) / 2;
if(citations[mid] == (length - mid)) return citations[mid];
else if(citations[mid] > (length - mid)) end = mid - 1;
else start = mid + 1;
}
return length - (end + 1);
}
}
