题目描述：

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.

题目大意：

H-Index的延伸：如果引用数组是递增有序的，你应该怎样优化算法？

提示：

期望运行时间复杂度为O(log n)，并且输入是递增有序的。

解题思路：

二分法（Binary Search），详见代码。

Python代码：

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

 

本文链接：http://bookshadow.com/weblog/2015/09/04/leetcode-h-index-ii/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码