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