quick select in python from CLRS


  • 0
    C

    Just to share my codes. Curious why it is shower than sorting and select?

    class Solution(object):
        def partition(self, A, p, r):
            x, i, j = A[p], p-1, r+1
            while True:
                i += 1
                while A[i]>x:
                    i += 1
                    
                j -= 1
                while A[j]<x:
                    j -= 1
                    
                if i < j:
                    A[i], A[j] = A[j], A[i]
                else:
                    return j
                    
        def helper(self, A, p, r, k):
            if p==r:
                return A[p]
            
            q = self.partition(A, p, r)
            N = q-p+1
            if N>=k:
                return self.helper(A,p, q, k)
            else:
                return self.helper(A, q+1, r, k-N)
            
        def findKthLargest(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: int
            """
            return self.helper(nums, 0, len(nums)-1, k)
    

Log in to reply
 

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