Kth Largest Element in an Array

Problem: Kth Largest Element in an Array

Actually there's worst-case linear time selection in algorithm textbooks. However that algorithm is somehow tedious and hard to implement. So it's better for us to use quick-sort to implement this selection.

Code in Python:

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        pos = self.partition(nums, 0, len(nums)-1)
        if pos > len(nums) - k:
            return self.findKthLargest(nums[:pos], k-(len(nums)-pos))
        if pos < len(nums) - k:
            return self.findKthLargest(nums[pos+1:], k)
        return nums[pos]

    def partition(self, nums, l, r):
        pivot = nums[r]
        pos = l
        for i in xrange(l, r):
            if nums[i] < nums[r]:
                nums[i], nums[pos] = nums[pos], nums[i]
                pos += 1
        nums[pos], nums[r] = nums[r], nums[pos]
        return pos

Note that we do all the operation in order thus reduce time and space cost. Besides, this partition method is quite useful in a lot of situations.