Top K Frequent Elements
给定一个整数数组 nums 和一个整数 k。返回 nums 中出现频率最高的 k 个值，按频率从高到低排列。如果两个值出现的次数相同，则较小的值排在前面。
无论某个值在 nums 中出现多少次，它在答案中只出现一次，并且 k 不会大于不同值的数量。
函数
- numsinteger-array
- 要计数的值
- kinteger
- 要返回多少个值
- 返回值integer-array
- 按频率从高到低排列的 k 个值，频率相同时较小的值排在前面
约束条件
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ k，并且k不超过nums中不同值的数量。
示例
- 输入
- nums = [4, 1, 4, 2, 1, 4, 3, 1, 4]k = 2
- 输出
- [4, 1]
- 解释
4出现了 4 次，1出现了 3 次，2和3各出现了 1 次。出现次数最多的两个值依次是4和1。
- 输入
- nums = [5, -2, 7, -2, 7, 5, 9]k = 2
- 输出
- [-2, 5]
- 解释
-2、5和7各出现两次，9出现一次。出现次数最多的值有三个并列，因此较小的两个值-2和5就是答案。
- 输入
- nums = [8]k = 1
- 输出
- [8]
- 解释
- 只有一个值，所以它是出现频率最高的值。
提示
逐个打开提示，每个都会多透露一点。
先找出每个值出现的频率。哪种数据结构能在一次遍历中将值映射到其计数？
有了计数后，你想按同一规则选出最好的
k个值：计数较大的排在前面，计数相同时值较小的排在前面。对每个不同的值进行排序也可以。大小为k的最小堆只保留仍有可能进入答案的值。计数是从 1 到
n的整数。为每个计数创建一个桶，桶c存放恰好出现c次的值，然后从计数最高的桶开始向下读取。按从小到大的顺序遍历这些值来填充桶，这样每个桶中的值已经按并列顺序排列。
题解
用哈希映射遍历一次，就能统计每个值。然后选出最好的 k 个：对全部 d 个不同的值排序，耗时为 O(d log d)；使用大小为 k 的最小堆，耗时为 O(d log k)；由于计数范围是从 1 到 n，桶排序可以按计数对这些值排序，且不需要比较。
先计数，再按计数排序
思路
用哈希表计数：[4, 1, 4, 2, 1, 4, 3, 1, 4]得到4 → 4、1 → 3、2 → 1、3 → 1。然后按计数从高到低、按值从低到高对不同的值排序。这个比较规则正好就是答案的顺序，因此前k个条目就是答案。
对d个不同的值排序需要O(d log d)的开销；对于 10^4 个不同的值，大约需要 1.3 × 10^5 次比较。当只需要前k个值时，这种方法仍会对所有值排序。
算法
- 统计哈希映射中每个值的出现次数。
- 将不同的值放入列表。
- 按出现次数从高到低排序，出现次数相同时按值从低到高排序。
- 返回前
k个值。
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Most frequent first; equal counts put the smaller value first.
ordered = sorted(counts, key=lambda value: (-counts[value], value))
return ordered[:k]在最小堆中保留最佳的 k 个
思路
只保留 k 个候选值。只有当新值优于最弱的候选值时，才保留它。较弱指计数更低，或者计数相同但值更大。按此规则排序的最小堆会将最弱值放在堆顶，读取堆顶的时间复杂度为 O(1)，替换堆顶的时间复杂度为 O(log k)。如果某个值不优于堆顶，就可以丢弃它，因为已经保留了 k 个更优的值。
堆只进行了部分排序，而且弹出时会先返回最弱的值，所以要从最后一个位置开始，倒序写入答案。选择候选值的时间复杂度为 O(d log k)，当 k 远小于 d 时，这比排序更快。
算法
- 统计哈希表中每个值的出现次数。
- 对于每个不同的值，如果堆中的值少于
k个，就将它推入堆中。 - 堆满后，将该值与堆顶的值（当前保留值中最弱的值）进行比较。如果新值更强，就将它放到堆顶，然后向下筛选。
- 弹出堆
k次，从答案的最后一个位置开始，依次向前写入每个值。
import heapq
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Entries are (count, -value). heapq keeps the smallest entry on top, which is
# the weakest value kept: the lowest count, and on a tie the larger value.
heap = []
for value, count in counts.items():
heapq.heappush(heap, (count, -value))
if len(heap) > k:
heapq.heappop(heap)
# Pops come out weakest first, so fill the answer from the back.
result = [0] * k
for i in range(k - 1, -1, -1):
result[i] = -heapq.heappop(heap)[1]
return result统计数量，然后按数量分桶排序
思路
计数是从 1 到 n 的整数，因此把每个值放进对应计数的桶中，再从 n 开始向下读取这些桶。这样会先得到出现频率最高的值，而且不会比较任何两个计数。
为了按规则处理并列情况，用一个包含 R = 2 × 10^4 + 1 个计数器的数组进行计数，将值 v 存在索引 v + 10^4 处，然后从最小值开始遍历数组，把每个值追加到对应的桶中。这样每个桶中的值都会按升序排列，这就是并列时的顺序。在第二个示例中，遍历会把 -2、5、7 放进桶 2，而 k = 2 会取出 -2 和 5。
总时间复杂度为 O(n + R)。如果用哈希表代替数组，桶会按映射中的顺序填充，因此每个桶都需要排序。
算法
- 将数组中的每个值都计数，并将其索引为
value + 10^4。 - 创建从 1 到
n的桶，每种可能的计数对应一个列表。 - 从最小值到最大值遍历计数数组，并将每个出现过的值添加到对应计数的桶中。
- 从计数为
n的桶开始，按计数从高到低读取桶中的值，直到取得k个值。
def topKFrequent(nums, k):
OFFSET = 10000 # values run from -10^4 to 10^4
counts = [0] * (2 * OFFSET + 1)
for x in nums:
counts[x + OFFSET] += 1
# buckets[c] lists the values that occur exactly c times. Walking the
# values from smallest to largest fills every bucket in ascending order.
buckets = [[] for _ in range(len(nums) + 1)]
for i, c in enumerate(counts):
if c > 0:
buckets[c].append(i - OFFSET)
# Read the buckets from the highest count down until k values are taken.
result = []
for c in range(len(nums), 0, -1):
for value in buckets[c]:
result.append(value)
if len(result) == k:
return result
return result
易错点和边界情况
- 按首次出现顺序或哈希映射的顺序打破平局。在第二个示例中，
-2、5和7都出现了两次，只有较小值优先的规则会得到[-2, 5]。 - 直接返回堆当前的数组。堆顶是最弱的值，也就是应该排在最后的值。
- 弄反堆的平局规则。对于按
(count, value)排序的最小堆，计数相同时会移除较小的值；应使用(count, -value)。 - 只创建与不同值数量相同的桶。在
[3, 3, 3, 3]中，一个值出现了n次，因此必须有桶n。 - 在 Java 中，使用
!=比较两个Integer计数。这会比较引用，计数超过 127 后就会出错。
常见问题3
“前 K 个高频元素”的时间复杂度是多少？
计数需要 O(n)。接着选出前 k 个值，如果对 d 个不同的值进行排序，耗时为 O(d log d)；如果使用大小为 k 的最小堆，耗时为 O(d log k)；如果使用桶排序遍历一次计数，则耗时为线性时间。由于 d 最多可达 n，最坏情况下排序的时间复杂度为 O(n log n)，而桶排序是线性的。
前 K 个高频元素问题可以在 O(n) 时间内解决吗？
是的，使用桶排序，因为计数是从 1 到 n 的整数。对计数使用 Quickselect，平均时间复杂度也是 O(n)，但最坏情况下是平方级。
为什么使用最小堆，而不是最大堆？
包含所有 d 个值的最大堆也可以：在 O(d) 时间内构建，然后弹出 k 次，总时间为 O(d + k log d)。大小为 k 的最小堆只保存 k 个条目，适合逐个到来的值，因为堆顶就是待丢弃的候选值。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def topKFrequent(nums, k):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [4, 1, 4, 2, 1, 4, 3, 1, 4] k = 2
预期输出
[4, 1]