题目
给定整数数组 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
网友评论