题目
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)
