Kth Largest Element in an Array

Quick selection

class Solution(object):
    nums = None

    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """

        left = 0
        right = len(nums) - 1
        self.nums = nums

        while True:
            p = self.partition(left, right)

            if p == k-1:
                return self.nums[p]

            if p > k-1:
                right = p - 1
            else:
                left = p + 1



    def partition(self, left, right):
        l = left + 1
        r = right
        nums = self.nums
        pivot = nums[left]

        while l <= r:
            if nums[l] < pivot and nums[r] > pivot:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1

            if nums[l] >= pivot:
                l += 1

            if nums[r] <= pivot:
                r -= 1

        nums[left], nums[r] = nums[r], nums[left]
        return r