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

题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

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

方法一：大顶堆、API

• maxheap 建立的顶堆
• 循环遍历数组 nums，将元素的负值依次放入顶堆。此时，数组的最大值位于顶堆的顶点，但其值为原值的负数，其余同理
• 循环弹出顶堆的前 k-1 个值，即弹出数组的前 k-1 个最大值
• 此时顶堆的顶点即为第 k 个最大元素的负值，返回该值

class Solution(object):
    def findKthLargest(self, nums, k):
        maxheap = []
        for num in nums:
            heapq.heappush(maxheap, -num)
        for num in range(k-1):
            heapq.heappop(maxheap)
        return -maxheap[0]

方法二：快速排序

findKthLargest 函数：寻找数组中的第 K 个元素

• left 和 right 分别指向数组的首尾
• 循环直至输出第 K 个元素
  • index 调用 partition 函数获取本次基准元素的下标
  • 判断基准元素下标 index 是否为第 K 个元素，若是则直接返回值
  • 若下标小于 k-1，即该基准元素小于第K个最大元素。由于生成的是降序序列，那么此次应在该基准元素的右边继续寻找，所以 left 更新为基准元素下标 index 加一
  • 若下标大于 k-1，即该基准元素大于第K个最大元素。由于生成的是降序序列，那么此次应在该基准元素的左边继续寻找，所以 right 更新为基准元素下标 index 减一

partition 函数：确定基准元素处于序列中的位置，最终生成降序序列

• pivot 基准元素，设置为该次最左边的值 nums[left]
• index 下标，初始值为 left
• 循环遍历 [left+1, right]
  • 将大于基准值的元素放到下标较小处，那么小于基准值的元素被放到下标较大处
• 交换基准值与大于基准值的最后一个值得位置，使得基准值处于正确位置
• 返回该基准值得下标

class Solution(object):
    def findKthLargest(self, nums, k):
        left, right = 0, len(nums)-1
        while True:
            index = self.partition(nums, left, right)
            if index == k-1:
                return nums[index]
            elif index < k-1:
                left = index + 1
            else:
                right = index - 1 
    
    def partition(self, nums, left, right):
        pivot = nums[left]
        index = left
        for i in range(left+1, right+1):
            if nums[i] >= pivot:
                index += 1
                nums[index], nums[i] = nums[i], nums[index]
        nums[index], nums[left] = nums[left], nums[index]
        return index

例：[3,2,1,5,6,4], k = 2
left = 0，right = 5
index = partition(nums, 0, 5)：
pivot = 3，index = 0
i = 1：nums[1] = 2 < pivot = 3
i = 2：nums[2] = 1 < pivot = 3
i = 3：nums[3] = 5 ≥ pivot = 3 index = 1 nums = [3, 5, 1, 2, 6, 4]
i = 4：nums[4] = 5 ≥ pivot = 3 index = 2 nums = [3, 5, 6, 2, 1, 4]
i = 5：nums[5] = 4 ≥ pivot = 3 index = 3 nums = [3, 5, 6, 4, 1, 2]
nums = [4, 5, 6, 3, 1, 2]
index = partition(nums, 0, 5) = 3
......

相关知识

• 堆：
  大顶堆： 每个结点的值都大于或等于其左右孩子结点的值
  小顶堆： 每个结点的值都小于或等于其左右孩子结点的值

• heappush(heap, item)： heapq.heappush()
  向堆中添加新值，建立的是小顶堆。可以通过添加原值的负值达到某种意义上的建立大顶堆，因为此时位于顶点的值虽是添加值得最小值，但是是原值得最大值
  heap： 堆
  item： 元素

• heappop(heap)： heapq.heappop()
  从堆中弹出并返回最小值
  heap： 堆

• 快速排序：
  步骤：

  • 首先设置一个分界值也就是基准值又是也称为监视哨，通过该分界值将数据分割成两部分
  • 将大于或等于分界值的数据集中到右边，小于分界值的数据集中到左边。一趟排序过后，左边部分中各个数据元素都小于分界值，而右边部分中各数据元素都大于或等于分界值，且右边部分个数据元素皆大于左边所有数据元素
  • 然后，左边和右边的数据可以看成两组不同的部分，重复上述1和2步骤
  • 当左右两部分都有序时，整个数据就完成了排序

参考

代码相关：https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/cpython3java-1da-gen-dui-diao-ku-2shou-l-xveq/
堆：https://blog.csdn.net/sinat_34715587/article/details/89195447 https://blog.csdn.net/qq_38022469/article/details/123851001
快速排序：https://blog.csdn.net/qq_52595134/article/details/118943109