美文网首页
Leetcode-275题:H-IndexII

Leetcode-275题:H-IndexII

作者: 八刀一闪 | 来源:发表于2016-10-11 21:23 被阅读51次

    题目

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

    思路

        首先根据引用次数将输入排序,对于其中的第i个元素,它的引用次数为a[i],它右边的元素个数为j。如果j==a[i],那么这个就是所求,因为对于i右边的元素,比他们大的元素个数一定小于j;而对于i左面的元素,元素的值又一定比a[i]小。如果j>a[i],可知此时至少有a[i]个元素大于a[i],但是在i的右边可能有更好的解。如果j<a[i],可知此时至少有j个元素大于j,但是在i的左边可能有更好的解。

    代码

    class Solution(object):
    
        def binary_search(self, citations, l, r):
            if l > r:
                return 0
            m = l + (r-l)/2
            if citations[m] == len(citations)-m:
                return citations[m]
            elif citations[m] > len(citations)-m:
                return max(self.binary_search(citations, l, m-1), len(citations)-m)
            else:
                return max(self.binary_search(citations, m+1, r), citations[m])
    
        def hIndex(self, citations):
            """
            :type citations: List[int]
            :rtype: int
            """
            if citations==None or len(citations)==0:
                return 0
            return self.binary_search(citations,0,len(citations)-1)
    

    相关文章

      网友评论

          本文标题:Leetcode-275题:H-IndexII

          本文链接:https://www.haomeiwen.com/subject/oibbyttx.html