2015年11月5日星期四

Leetcode 275 H-Index II

Follow up for H-Index: What if the 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;  
   }  
 }  

没有评论:

发表评论