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


  • 0

    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
    

Log in to reply
 

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