Quick Select

一般题目中要求求出第k大或者第k小的元素的时候，可以用quick select算法在O(n)时间内得到结果，比用堆寻找更快，但是如果需要找出前k个时就不如用堆了，quick select的算法具体实现和快速排序的partition算法是一模一样的，除了找第k大时需要将比较的两个大于小于号换一下位置以外，下面是一道LeetCode原题：Kth Largest Element in an Array

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

        return self.quickSelect(nums, 0, n - 1, k)

    def quickSelect(self, nums, start, end, k):
        if start >= end:
            return nums[end]

        left, right = start, end
        pivot = nums[left + (right - left) / 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 += 1
                right -= 1

        if start + k - 1 <= right:
            return self.quickSelect(nums, start, right, k)

        if start + k - 1 >= left:
            return self.quickSelect(nums, left, end, k - (left - start))

        return nums[right + 1]