Leetcode 215


  Posted on 15 Feb 2017
quick sort


Tutorial


Using an algorithm like quick sort, except that it do not recursively search both half of the array, but only one half. Because the kth element could only be on one of the two halves of the array. It would make the complexity from to =. This algorithm is called quick selector.

Solution


class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return qsort(nums, k-1)
        
def qsort(nums, k):
    x = nums[0]
    l = 0
    r = len(nums) - 1
    while l < r:
        while l < r and nums[r] <= x:
            r -= 1
        nums[l] = nums[r]
        while l < r and nums[l] >= x:
            l += 1
        nums[r] = nums[l]
    nums[l] = x
    if l == k:
        return nums[l]
    if l > k:
        return qsort(nums[:l], k)
    return qsort(nums[l + 1:], k - l - 1)