275. H-Index II

  • 34.4%

https://leetcode.com/problems/h-index-ii/

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.


方法一:

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int hIndex(vector<int>& citations) {
if(citations.empty()) return 0;
int n = citations.size();
int left = 0, right = n-1;
while(left<=right){ // <= 不是 <
int mid = left + (right-left)/2;
if(citations[mid]>=n-mid){ // >= 而不是>
right = mid-1;
}else{
left = mid+1;
}
}
return n-left;
}
};

cpp

124ms, 60.19%, May.4th, 2016

https://leetcode.com/discuss/56109/space-easy-solution-with-detailed-explanations-java-python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int hIndex(vector<int>& citations) {
int size = citations.size();

int first = 0;
int mid;
int count = size;
int step;

while(count > 0){
step = count / 2;
mid = first + step;
if(citations[mid] < size - mid){
first = mid + 1;
count -= (step + 1);
}
else count = step;
}

return size - first;
}
};

python

124ms, 60.19%, 82 / 82, May.4th, 2016

https://leetcode.com/discuss/56119/binary-search-in-python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
N = len(citations)
low, high = 0, N - 1
while low <= high:
mid = (low + high) / 2
if N - mid > citations[mid]:
low = mid + 1
else:
high = mid - 1
return N - low

132ms, 46.76%, May.4th, 2016

https://leetcode.com/discuss/56109/space-easy-solution-with-detailed-explanations-java-python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
length = len(citations)

first = 0
count = length

while count > 0:
step = count / 2
mid = first + step
if citations[mid] < length - mid:
first = mid + 1
count -= (step + 1)
else:
count = step

return length - first

java

12ms, 46.91%, May.4th, 2016

https://leetcode.com/discuss/56109/space-easy-solution-with-detailed-explanations-java-python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public int hIndex(int[] citations) {
int len = citations.length;

int first = 0;
int mid;
int count = len;
int step;

while (count > 0) {
step = count / 2;
mid = first + step;
if (citations[mid] < len - mid) {
first = mid + 1;
count -= (step + 1);
}
else {
count = step;
}
}

return len - first;
}
}
谢谢你,可爱的朋友。