问题描述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

解题思路

首先能想到的是最笨的方法，即，我们先将整个数组进行排序，然后取倒数第k个数。但是，再我将代码写好后，提交到 leetcode上时，我发现它会提示我“超时”(-v-)...
然后我就去看了其他人的一些思路，比较典型的就有堆排序算法以及快速选择算法。下面就来介绍一下这两种算法。

• 第一种堆排序算法就是，我们先建立一个大顶堆，令它的大小小于或者等于k，然后遍历整个数组，将数组中大于堆中最小元素的数的放入堆中，如果堆已满，则踢出其中较小的元素，最后得到的堆中最小的元素就是要求得的第K大的元素。
• 第二种算法是快速选择算法，在本科的时候，我们学过快排，其思想是选择一个枢纽，把大于该枢纽的数放在它的右边，小于它的数放在它的左边，然后对于左边的数和右边的数依次递归进行过该算法。在这里我们并不需要递归进行该算法，我们只需要计算右边的部分，当某次排序后右边部分数的数量小于k，那么对前一次的数组进行排序，取出第-k的数即可。

具体代码

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        #返回数组中第k个最大元素，也就是数组升序排序后，从右往左数的第k个数字

        # # 法1.使用Python内置的sorted，这个得知道
        # return sorted(nums)[-k]

        # # 法2.调用包，使用堆排序，速度相当快。
        # import heapq
        # return heapq.nlargest(k,nums)[-1];

        # 法3.使用堆排序：查找第k大的数值
        def maxHeapify(nums, st_idx, ed_idx):
            # 最大堆调整，将堆的末端子节点作调整，使得子节点永远小于父节点
            index = st_idx
            # 不断地向下调整
            while True:
                index = 2 * st_idx + 1
                # 如果调整到最后部分，就跳出
                if index > ed_idx:
                    break
                # 如果左孩子小于右孩子，则index变成右孩子
                if index + 1 <= ed_idx and nums[index + 1] > nums[index]:
                    index += 1
                # 如果左孩子大于父节点，则互换
                if nums[index] > nums[st_idx]:
                    nums[st_idx], nums[index] = nums[index], nums[st_idx]
                    st_idx = index
                else:
                    break
        # 创建大根堆
        for idx in range((len(nums) - 2) // 2, -1, -1):
            maxHeapify(nums, idx, len(nums) - 1)

        # 交换堆顶与堆尾 
        for head_end in range(len(nums)-1, 0, -1):
            nums[head_end], nums[0] = nums[0], nums[head_end]
            maxHeapify(nums, 0, head_end-1)
            if len(nums)-head_end == k:      # 遇到倒序个数就是k的话就返回
                return nums[head_end]      
        return nums[0]                     

class Solution:
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def partition(left, right, pivot_index):
            pivot = nums[pivot_index]
            nums[pivot_index], nums[right] = nums[right], nums[pivot_index]  
            
         
            store_index = left
            for i in range(left, right):
                if nums[i] < pivot:
                    nums[store_index], nums[i] = nums[i], nums[store_index]
                    store_index += 1

            nums[right], nums[store_index] = nums[store_index], nums[right]  
            
            return store_index
        
        def select(left, right, k_smallest):
            
            if left == right:     
                return nums[left]  
            
            pivot_index = random.randint(left, right)     
                                  
            pivot_index = partition(left, right, pivot_index)
            
            if k_smallest == pivot_index:
                 return nums[k_smallest]
            elif k_smallest < pivot_index:
                return select(left, pivot_index - 1, k_smallest)
            else:
                return select(pivot_index + 1, right, k_smallest)

        return select(0, len(nums) - 1, len(nums) - k)