卖萌的弱渣

I am stupid, I am hungry.

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.

Solution

  • Binary Search: if citations[mid] < len(citations)-mid, start=mid+1
(H-Index2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        start = 0
        end = len(citations)-1

        while start <= end:
            mid = (start + end)/2
            if citations[mid] < len(citations)-mid:
                start = mid+1
            else:
                end = mid-1
        return len(citations)-start