Kth Largest Element in an Array
给你一个整数数组 nums 和一个整数 k。返回 nums 中第 k 大的值：将数组按从大到小排序后，从 1 开始计数，位于第 k 个位置的值。
相同的值要分别计数。在 [5, 5, 1] 中，最大的值是 5，第二大的值也是 5。
函数
- numsinteger-array
- 要排序的值
- kinteger
- 要返回哪个最大值，1 表示最大的值
- 返回值integer
- 第 k 大的值，重复值也计入
约束条件
1 ≤ k ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 104- 相等的值也会分别计数。
示例
- 输入
- nums = [7, 2, 9, 4, 9, 1]k = 2
- 输出
- 9
- 解释
- 从大到小排列，这些值是
9, 9, 7, 4, 2, 1。两个 9 分别计数，因此第二大的值是9，不是7。
- 输入
- nums = [5, -3, 8, 0, 2]k = 4
- 输出
- 0
- 解释
- 这些值从大到小依次是
8, 5, 2, 0, -3，其中第四个值是0。
- 输入
- nums = [6]k = 1
- 输出
- 6
- 解释
- 只有一个值且
k = 1时，这个值就是最大的。
进阶
现在，值会一次到达一个。你能在每个值到达后，用 O(log n) 的时间报告目前为止所有值的中位数吗？
提示
逐个打开提示，每个都会多透露一点。
按从大到小排序后，答案位于一个已知位置。是哪个位置？你需要知道其他所有值才能确定它吗？
第 k 大的值是最大的
k个值中最小的那个。如果你只保留目前为止见过的最大的k个值，那么遇到一个新值时，应该把它和其中的哪个值进行比较？维护一个最多包含
k个值的最小堆。新值更大时，就替换堆顶元素；最后堆顶元素就是答案。若要达到平均时间复杂度O(n)，可以像快速排序那样围绕随机枢轴进行分区，并只保留包含索引n-k的那一侧。
题解
你只需要排序后某一个位置的值，而不是全部 n 个值。大小为 k 的最小堆只保留仍有可能成为答案的值；快速选择像 quicksort 一样进行分区，但只处理包含答案的一侧，因此平均时间可以降到 O(n)。
排序并读取一个位置
思路
第 k 大的值由排序后的顺序决定，因此先排序，再读取一个位置：从大到小排序时读取索引 k-1，从小到大排序时读取索引 n-k。按从大到小的顺序排序后，第一个示例为 [9, 9, 7, 4, 2, 1]，索引 1 处的值是第二个 9。每个重复的值都有自己的位置。
当 n = 10^4 时，排序大约需要进行 1.3 × 10^5 次比较，也就是在只关心一个位置时，仍要对全部 n 个值排序。
算法
- 复制
nums，这样调用者的数组就能保持原样。 - 对副本进行排序。使用数值比较；有些语言默认会把数字当作文本来比较。
- 按从大到小的顺序返回索引
k-1处的值，或者按从小到大的顺序返回索引n-k处的值。
def findKthLargest(nums, k):
# Largest first: the k-th largest sits at index k-1.
ordered = sorted(nums, reverse=True)
return ordered[k - 1]在最小堆中保留最大的 k 个元素
思路
第 k 大的值是最大的 k 个值中最小的那个。因此，只需遍历一次 nums，并用小顶堆保留目前为止见到的最大的 k 个值，堆顶就是其中最小的值。
堆中有 k 个值后，将每个新值 x 与堆顶比较。如果 x 不比堆顶大，那么已有 k 个值至少和它一样大，因此 x 不可能成为答案。如果 x 更大，那么堆顶就会被排出最大的 k 个值，x 则替换它。在示例 2 中，当 k = 4 时，前四个值入堆后的堆顶是 -3；2 替换了它，而新的堆顶 0 就是答案。
每个值最多需要进行一次 O(log k) 的堆操作：时间复杂度为 O(n log k)，空间复杂度为 O(k)。
算法
- 从一个空的最小堆开始。
- 对于每个值
x，当堆中的值少于k个时，将它添加到堆中。 - 堆中有
k个值后，只有当x大于堆顶时，才用x替换堆顶。 - 处理完最后一个值后，返回堆顶。
import heapq
def findKthLargest(nums, k):
# A min-heap of the k largest values so far; its top is the smallest of them.
heap = []
for x in nums:
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]:
heapq.heapreplace(heap, x) # drop the top, add x
return heap[0]使用三路分区的快速选择
思路
经过一次快速排序分区后，枢轴会位于最终的排序索引上，但两侧都还没有排好序。按从小到大的顺序，答案位于 target = n-k，因此每次分区后，你只需继续处理包含 target 的那一侧。
在第一个示例中，target 是 4。以 4 为枢轴分区后，7, 9, 9 位于索引 3 到 5，因此你保留这一侧。再以 9 为枢轴对这一侧分区后，两个 9 都位于索引 4 和 5，答案就在索引 4。
三路分区会将等于枢轴的值归为一组，放在 [lt, gt] 中，它们已经处于排序后的正确位置，因此如果 target 在其中，搜索就可以结束。随机选择的枢轴有一半的概率落在中间一半，因此范围最多缩小到原来的四分之三，所以期望工作量为 O(n)；最坏情况下仍为 O(n²)。对副本进行分区需要 O(n) 的内存。
算法
- 将
nums复制到a，设置target = n-k、lo = 0和hi = n-1。 - 从
a[lo..hi]中随机选择一个枢轴。 - 将
a[lo..hi]中的值划分为小于、等于和大于枢轴的几组，并将等于枢轴的值留在a[lt..gt]中。 - 如果
target < lt，设置hi = lt-1；如果target > gt，设置lo = gt+1；否则返回枢轴。 - 从第 2 步开始重复。
import random
def findKthLargest(nums, k):
a = list(nums)
target = len(a) - k # the answer's index once a is sorted smallest first
lo, hi = 0, len(a) - 1
while True:
pivot = a[random.randint(lo, hi)]
# Three-way partition of a[lo..hi]: < pivot, then == pivot, then > pivot.
lt, i, gt = lo, lo, hi
while i <= gt:
if a[i] < pivot:
a[lt], a[i] = a[i], a[lt]
lt += 1
i += 1
elif a[i] > pivot:
a[i], a[gt] = a[gt], a[i]
gt -= 1
else:
i += 1
# Now a[lt..gt] all equal pivot, and they are in their sorted places.
if target < lt:
hi = lt - 1
elif target > gt:
lo = gt + 1
else:
return pivot
易错点和边界情况
- 先移除重复值。在第一个示例中，答案是
9，但将数组转换为集合后，答案就变成了7。 - 读取索引
n-k-1。k从 1 开始计数，因此按从小到大的顺序排列时，答案位于n-k处。 - 将数字按文本排序。在 JavaScript 和 TypeScript 中，
[10, 9, 2].sort()会得到[10, 2, 9]；传入(a, b) => a - b。 - 使用大小为
k的最大堆。移除最大值可以保留最小的k个值，并返回第k小的值。 - 使用带双向分区或固定枢轴的 Quickselect。
10^4个7的副本，或一个已排序的数组，会导致每轮只缩小一个值的范围：大约需要5 × 10^7步。
常见问题4
数组中第 K 大元素的时间复杂度是多少？
排序需要 O(n log n) 时间。大小为 k 的最小堆需要 O(n log k) 时间和 O(k) 内存。使用随机枢轴的快速选择算法平均需要 O(n) 时间，最坏情况下需要 O(n²)，但随机枢轴会让这种情况极不可能发生。
为什么用最小堆而不是最大堆来查找第 k 大的元素？
你用来比较并移除的值是最大的 k 个值中最小的那个，因此它必须位于堆顶。只有把全部 n 个值都放入最大堆，再弹出 k-1 次，才能实现这一点，但这需要 O(n) 的内存。
求第 k 大元素时，我应该使用堆还是快速选择？
Quickselect 的平均速度更快，时间复杂度为 O(n)，但它需要将所有值保存在内存中，并会对它们重新排序。堆的时间复杂度为 O(n log k)，没有糟糕的最坏情况，而且适用于值逐个到达的情况。
能否在最坏情况下以线性时间找到第 k 大的元素？
是的。中位数的中位数规则会选出一个枢轴，保证划分掉固定比例的值，因此选择操作在最坏情况下的时间复杂度为 O(n)，不过实际运行时速度较慢。对于范围从 -10^4 到 10^4 的值，统计每个值也能在线性时间内完成。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def findKthLargest(nums, k):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [7, 2, 9, 4, 9, 1] k = 2
预期输出
9