[LeetCode]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.

题目大意:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

暂无评论

张贴您的评论