題目

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

思路

????首先根據(jù)引用次數(shù)將輸入排序，對于其中的第i個元素，它的引用次數(shù)為a[i]，它右邊的元素個數(shù)為j。如果j==a[i]，那么這個就是所求，因為對于i右邊的元素，比他們大的元素個數(shù)一定小于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)