Leetcode-275题:H-IndexII

题目

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)