Skip to content

215. Kth Largest Element in an Array


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 O(N log N) to O(N + N/2 + N/4 + ...)=O(N). This algorithm is called quick selector.


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)