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