原题

在数组中找到第k大的元素

给出数组[9,3,2,4,8]，第三大的元素是4
给出数组[1,2,3,4,5]第一大的元素是5，第二大的元素是4，第三大的元素是3，以此类推

解题思路

• 寻找第k大的数字可以转化为寻找第n+1-k小的数字，进而想到Quick Select

• Quick Select算法的基本思路与Quick Sort类似，重点是partition

• 基本思想，随机选取一个pivot，小于的放左边，大于等于的放右边，返回pivot的位置

• 如果pivot == k，则正好找到了第k小的元素

• 如果pivot > k，则第k小的元素存在于pivot左边

• 如果pivot < k，则第k小的元素存在于pivot右边

• 时间复杂度：O(n logn) (in quicksort), O(n) (in quickselect)

• 方法二：Min Heap，维护一个大小为k的minHeap

完整代码

Method 1
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        # convert the kth largest to smallest
        return self.findKthSmallest(nums, len(nums)+1-k)

    def findKthSmallest(self, nums, k):
        if nums:
            pos = self.partition(nums, 0, len(nums)-1)
            if k > pos+1:
                return self.findKthSmallest(nums[pos+1:], k-pos-1)
            elif k < pos+1:
                return self.findKthSmallest(nums[:pos], k)
            else:
                return nums[pos]

    # choose the right-most element as pivot   
    def partition(self, nums, l, r):
        low = l
        while l < r:
            if nums[l] < nums[r]:
                nums[l], nums[low] = nums[low], nums[l]
                low += 1
            l += 1
        nums[low], nums[r] = nums[r], nums[low]
        return low

# Method 2
import Queue
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        minHeap = Queue.PriorityQueue()
        for num in nums:
            if minHeap.qsize() < k:
                minHeap.put(num)
            elif num > minHeap.queue[0]:
                minHeap.get()
                minHeap.put(num)
        
        return minHeap.queue[0]