Follow up for H-Index: What if the citations
array is sorted in ascending order? Could you optimize your algorithm?
一刷
令len-h = left, 则N-left = h
用binary search在数组中寻找，nums[left]为小于h和大于h的交界。return len-left
public class Solution {
public int hIndex(int[] citations) {
int left = 0, len = citations.length, right = len-1, mid;
while(left<=right){
mid = left + (right-left)/2;
if(citations[mid]>=(len-mid)) right = mid-1;
else left = mid+1;
}
return len-left;
}
}
二刷
思路和1刷相同
public class Solution {
public int hIndex(int[] citations) {
int left = 0, len = citations.length, right = len-1, mid;
while(left<=right){
mid = left + (right-left)/2;
if(citations[mid] >(len-mid)) right = mid-1;
else if(citations[mid] <(len-mid)) left = mid+1;
else return len-mid;
}
return len - left;
}
}
三刷
同上
public class Solution {
public int hIndex(int[] citations) {
int left = 0, len = citations.length, right = len-1, mid;
while(left<=right){
mid = left + (right-left)/2;
if(citations[mid] >=(len-mid)) right = mid-1;
else if(citations[mid] <(len-mid)) left = mid+1;
}
return len - left;
}
}
