215. Kth Largest Element in an Array

Problem Link

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 $O(N log N)$ to $O(N + N/2 + N/4 + ...)$=$O(N)$. 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)