O(n) time and O(1) space Solution with Partition Algorithm

• We can use the Partition Algorithm to do this in O(n) time (Avg.) and O(1) extra space.
The practical performance of this algorithm could be improved by a good `pivot` select function. Here, I choose the first element of the array as the `pivot`.

``````class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
def partition(nums, start, end):
pivot = nums[start]
left = start
right = end
while left < right:
while left < right and nums[right] <= pivot:
right -= 1
nums[left] = nums[right]
while left < right and nums[left] >= pivot:
left += 1
nums[right] = nums[left]
nums[left] = pivot
return left

if not citations:
return 0
lo = 0
hi = len(citations) - 1
while lo <= hi:
index = partition(citations, lo, hi)
# condition:  h of his/her N papers have at least h citations each
if citations[index] >= index+1:
lo = index + 1
else:
hi = index - 1
return hi + 1
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.