275.H-Index II

Tags: [sort], [binary_search], [trick]

Com: {fb}

Link: https://leetcode.com/problems/h-index-ii/\#/description

Follow up for H-Index: What if the citationsarray is sorted in ascending order? Could you optimize your algorithm?

Solution: Binary Search

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        if not citations:
            return 0

        size = len(citations)
        left = 0
        right = size - 1
        while left <= right:
            mid = left + (right - left) / 2
            bottom_len = size - mid
            if citations[mid] >= bottom_len:
                if mid - 1 < left or citations[mid - 1] < (size - (mid - 1)):
                    return bottom_len

                right = mid - 1
            else:
                left = mid + 1

        return 0

Revelation:

• Find the max area square, see the following pics:

Note:

• Time complexity = O(lgn), n is the number of elements of the given citations.
• Space complexity = O(1).