LeetCode 215 数组中的第K个最大元素

题目大意：
从未排序数组中找最大的第K个元素。

题目分析：
大概有三种思路：

1. 直接排序，取第K大的，时间复杂度是O(nlogn)
2. 借鉴快速排序的思想。选取一个参考点（pivot），每次迭代，将它放到排序后应在的位置，将比它大、比它小的分别放到它的两边。每次迭代后，根据pivot的位置，可以将它左边或者右边的舍弃。因此平均时间负责度= n + n/2 + n/4 …… = O(n)。
3. 创建一个大小为K的堆，构成一个最小堆，做堆排序。时间复杂度是O(nlogK)

代码(Python3)：

最后选择第二种思路

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        idx, num = self.partition(nums, 0, len(nums)-1)
        while(True):
            if idx == k-1:
                return num
            else:
                if idx > k-1:
                    idx, num = self.partition(nums, 0, idx-1)
                else:
                    idx, num = self.partition(nums, idx+1, len(nums)-1)
                     
        return 0
    def partition(self, nums, start, end):
        # print (start, end)
        if (end == start):
            return start, nums[start]
        i = start + 1
        j = end
        while(True):
            while(i < len(nums)-1 and nums[i] >= nums[start]):
                i += 1
            while(j > start and nums[j] <= nums[start]):
                j -= 1
            
            if j <= i: #第25行在这！
                nums[start], nums[j] = nums[j], nums[start]
                break
            else:
                nums[i], nums[j] = nums[j], nums[i]
            # print (nums, j, nums[j])
        # print('***')
        # print (nums, j, nums[j])
        return j, nums[j]   

需要注意几点：

1. 第8行，最后一个参数不能写成idx，否则遇到只有两个元素的子数组，就死循环了。第10行同理。
2. 第20行和22行，要加边界判别条件，否则以降序排序为例，遇到一个升序数组，i直接就越界了；遇到降序数组，j也越界了。
3. 第25行，不能不写等号。否则，以降序排序为例，遇到一个升序数组，j不会动，而i会移动到j的位置，如果不加等号的话，执行不到break。

最后，这是第三种思路的代码：

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return heapq.nlargest(k, nums)[-1]