5.第K大元素

• 描述
  在数组中找到第k大的元素。
  给出数组 [9,3,2,4,8]，第三大的元素是 4。
• Solution
  使用快排Partition，得到基轴，如果k>基轴，就在基轴左边进行Partition迭代，如果k<基轴，就在基轴右边进行Partition迭代。

Partition

1. 取一元素作为轴点pivot
2. 从数组的左右端 left = 0 和 right = len(nums) - 1 开始扫描，如果nums[i] > pivot，则right -= 1，<同理，left += 1
3. 将扫描到的数进行调换，在进行迭代，最终right=left

class Solution:
    # @param k & A a integer and an array
    # @return ans a integer
    def kthLargestElement(self, k, A):
        if not A or k < 1 or k > len(A):
            return None
        return self.partition(A, 0, len(A) - 1, len(A) - k)
        
    def partition(self, nums, start, end, k):
        """
        During the process, it's guaranteed start <= k <= end
        """
        if start == end:
            return nums[k]
            
        left, right = start, end
        pivot = nums[(start + end) // 2]
        while left <= right:
            while left <= right and nums[left] < pivot:
                left += 1
            while left <= right and nums[right] > pivot:
                right -= 1
            if left <= right:
                nums[left], nums[right] = nums[right], nums[left]
                left, right = left + 1, right - 1
             
        if k <= right:
            return self.partition(nums, start, right, k)
        if k >= left:
            return self.partition(nums, left, end, k)
        
        return nums[k]