Two solutions: O(log n), O(n)


  • 3
    J
    1. O(lg n)

       int hIndex(vector<int>& citations) {
         int left = 0;
          int right = citations.size() - 1;
         int n = citations.size();
         int last = 0;
      
         while (left <= right) {
        	  int mid = left + (right - left) / 2;
      	  if (citations[mid] == n - mid)
      	  	return n - mid;
      
      	  if (n - mid < citations[mid]) {
      		right = mid - 1;
      		last = n - mid;
      	  }
      	  else
      		left = mid + 1;
         }
      
         return last;
       }
      
    1. O(n)

       int hIndex(vector<int>& citations) {
          int n = citations.size();
          for(int i = 0; i<citations.size(); i++) {
             if(n - i <= citations[i])
                  return n - i;
          }
       
          return 0;
       }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.