Python min-heap and quick partition solutions (O(nlogn) and O(n) time complexities).


  • 8
    C
    # k+(n-k)*log(k) time
    def findKthLargest1(self, nums, k):
        heap = nums[:k]
        heapq.heapify(heap)  # create a min-heap whose size is k 
        for num in nums[k:]:
            if num > heap[0]:
               heapq.heapreplace(heap, num)
            # or use:
            # heapq.heappushpop(heap, num)
        return heap[0]
      
    # O(n) time, quicksort-Partition method   
    def findKthLargest(self, nums, k):
        pos = self.partition(nums, 0, len(nums)-1)
        if pos > len(nums) - k:
            return self.findKthLargest(nums[:pos], k-(len(nums)-pos))
        elif pos < len(nums) - k:
            return self.findKthLargest(nums[pos+1:], k)
        else:
            return nums[pos]
     
    # Lomuto partition scheme   
    def partition(self, nums, l, r):
        pivot = nums[r]
        lo = l 
        for i in xrange(l, r):
            if nums[i] < pivot:
                nums[i], nums[lo] = nums[lo], nums[i]
                lo += 1
        nums[lo], nums[r] = nums[r], nums[lo]
        return lo

  • 0
    H

    Why quicksort-Partition method is O(n) time? should it be O(n2) the worst case??If it's a sorted array. and k = 1.
    Btw, we can construct a heap with n_size, then the time complexity is O(n+klogn) which is better than a k_size heap at most cases.


  • 0
    H

    Actually, I think quicksort way should be O(kn) in this problem


  • 0
    C

    The quicksort-Partition solution every time we just need to sort half of the remaining list, so the time complexity should be n+n/2+n/4+...=2n, which is O(n).


  • 0
    H

    but how could you know your pivot is the middle big one?


  • 0
    C

    Yes, if the pivot is not the middle one then the time complexity should be larger than O(n), while here is the average case.


Log in to reply
 

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