Follow up for : What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Hint:

1. Expected runtime complexity is in O(log n) and the input is sorted.

 的拓展。输入的数组是有序的，让我们优化算法。提示(现在题目中没有提示了)：O(logn)。

显然使用二分法。

 

Python:

class Solution(object):    def hIndex(self, citations):        """        :type citations: List[int]        :rtype: int        """        n = len(citations)        left, right = 0, n - 1        while left <= right:            mid = (left + right) / 2            if citations[mid] >= n - mid:                right = mid - 1            else:                left = mid + 1        return n - left

C++:

class Solution {public:    int hIndex(vector
     
      & citations) {        int len = citations.size(), left = 0, right = len - 1;        while (left <= right) {            int mid = 0.5 * (left + right);            if (citations[mid] == len - mid) return len - mid;            else if (citations[mid] > len - mid) right = mid - 1;            else left = mid + 1;        }        return len - left;    }};　
     

 

类似题目：