leetcode 215 数组中第K大的元素

有两种方法解决：

1. 使用堆，维持一个k大小的最大堆， 依次出堆，返回最后的元素！！！ 或者直接将列表转换成堆，在出堆 k 次。

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        import heapq
        heapq.heapify(nums)
        for i in range(len(nums) + 1 -k):
            t = heapq.heappop(nums)
        return t

2. 快排思想，复杂度为 n。先将第 k 大的元素转换成 第 i = len(nums)+1-k 小的元素，然后用快排思想随机将一个元素排好位，判断转换后的第 i 个元素与快排排好的元素的关系。

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return self.findKthLargestHelper(nums, 0, len(nums) - 1, len(nums) + 1 - k)

    def findKthLargestHelper(self, nums, p, r, i):
        if p == r:
            return nums[p]
        q = self.randomPartation(nums, p, r)
        k = q - p + 1
        if i == k:
            return nums[q]
        elif i < k:
            return self.findKthLargestHelper(nums, p, q-1, i)
        else:
            return self.findKthLargestHelper(nums, q+1, r, i-k)

    def randomPartation(self, nums, p, r):
        import random
        t = random.randint(p, r)
        nums[r], nums[t] = nums[t], nums[r]
        return self.partation(nums, p, r)

    def partation(self, nums, p, r):
        j = p - 1
        key = nums[r]
        for i in range(p, r):
            if nums[i] <= key:
                j += 1
                nums[i], nums[j] = nums[j], nums[i]
        nums[j+1], nums[r] = nums[r], nums[j+1]
        return j+1

上述中 k 是左半边元素个数，再加上1，表示包含主元的左半边元素个数。

上面不好理解，那就去掉 k 的步骤，看下面代码。

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return self.findKthLargestHelper(nums, 0, len(nums) - 1, len(nums) - k)

    def findKthLargestHelper(self, nums, p, r, i):
        if p == r:
            return nums[p]
        q = self.randomPartation(nums, p, r)
        if q < p or q > r:
            print('error')
        if q == i:
            return nums[q]
        elif q > i:
            return self.findKthLargestHelper(nums, p, q-1, i)
        else:
            return self.findKthLargestHelper(nums, q+1, r, i)

    def randomPartation(self, nums, p, r):
        import random
        t = random.randint(p, r)
        nums[r], nums[t] = nums[t], nums[r]
        return self.partation(nums, p, r)

    def partation(self, nums, p, r):
        j = p - 1
        key = nums[r]
        for i in range(p, r):
            if nums[i] <= key:
                j += 1
                nums[i], nums[j] = nums[j], nums[i]
        nums[j+1], nums[r] = nums[r], nums[j+1]
        return j+1