Amortized O(n) in-place Python using random-select


  • 0

    Every CS guy should know this when one studies quick sort.

    import random
    class Solution(object):
        # @param k & A a integer and an array
        # @return ans a integer
        def findKthLargest(self, A, k):
            return self.quickselect(0, len(A) - 1, A, len(A) - k)
            
        def quickselect(self, start, end, A, k):
            if start == end:
                return A[start]
                
            mid = self.partition(start, end, A)
            
            if mid == k:
                return A[k]
            elif mid > k:
                return self.quickselect(start, mid - 1, A, k)
            else:
                return self.quickselect(mid + 1, end, A, k)
            
        def partition(self, start, end, A):
            pivotIndex = random.randrange(start, end + 1)
            pivot = A[pivotIndex]
            A[end], A[pivotIndex] = A[pivotIndex], A[end]
            mid = start
            for i in xrange(start, end):
                if A[i] < pivot:
                    A[mid], A[i] = A[i], A[mid]
                    mid += 1
            A[mid], A[end] = A[end], A[mid]
            return mid
    

Log in to reply
 

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