Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?
Hint:
- Expected runtime complexity is in O(log n) and the input is sorted.
274. H-Index H指数 的拓展。输入的数组是有序的，让我们优化算法。提示(现在题目中没有提示了)：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<int>& 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;
}
};
类似题目：