Follow upfor H-Index: What if thecitationsarray is sorted in ascending order? Could you optimize your algorithm?
Hint:
Expected runtime complexity is inO(logn) and the input is sorted.
solution:
Binary search.
public int hIndex(int[] citations) { if(citations.length <=0) return 0; int len = citations.length; int start = 0; int end = len-1; while(start<=end) { int mid = start + (end-start)/2; if(citations[mid] == len-mid) return len-mid; else if (citations[mid] < len-mid) start = mid+1; else end = mid-1; } return len-start; }