citations
array is sorted in ascending order? Could you optimize your algorithm?Solution: we can use the linear solution I used in
274. H-Index
Or we can use a better binary search.
The same idea as we do the linear search.
length-m is the target we try to figure it out.
If current paper has the same citations (citations[m]) as the amount of paper that has at least current citations ( length-m), it means H-index is citations[m] because any larger h (index to right) will lead to less paper.
If length-m > current paper's citations, we should search right half because, length-m is too large that we can't find lenth-m of paper that have at least length-m citations. Because the most (length-m)th paper has citations of citations[m] which is less than length-m.
else if length-m < current paper's citations, we should search left half, because although it satisfy the requirement but it is not the optimal answer.
public int hIndex(int[] citations) {
int n=citations.length;
int l=0;
int r=n-1;
while(l<=r){
int m=(r-l)/2+l;
if(n-m==citations[m]) return n-m;
else if(n-m<citations[m]) r=m-1;
else l=m+1;
}
return n-l;
}
No comments:
Post a Comment