citations
array is sorted in ascending order? Could you optimize your algorithm?Solution 1: use binary search, can be solved in O(logn).
public class Solution {
public int hIndex(int[] citations) {
int n=citations.length;
int lo=0, hi=n;
while (lo<hi) {
int mid=lo+(hi-lo)/2;
if (citations[mid]>=n-mid) hi=mid;
else lo=mid+1;
}
return n-lo;
}
}
没有评论:
发表评论