# [LeetCode] 275. H-Index II H指数 II

2018/03/27 02:32

Follow up for H-Index: 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.

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;
}
};　``````

[LeetCode] 274. H-Index H指数

0
0 收藏

0 评论
0 收藏
0