quick select in python from CLRS

  • 0

    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]
                    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)
                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.