标签: 数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列）
难度: Medium
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:
输入: nums = [1], k = 1 输出: [1]
提示：
1 <= nums.length <= 105k 的取值范围是 [1, 数组中不相同的元素的个数]k 个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
运行时间: 20 ms
内存: 19.3 MB
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
map_fre = defaultdict(int)
for i in range(len(nums)):
map_fre[nums[i]] += 1
pri_que = []
for key,freq in map_fre.items():
heapq.heappush(pri_que,(freq,key))
if len(pri_que) > k:
heapq.heappop(pri_que)
result = [0]*k
for i in range(k-1,-1,-1):
result[i] = heapq.heappop(pri_que)[1]
return result
该题解的思路是先用哈希表统计每个元素出现的频率，然后用小顶堆维护前 k 个高频元素。具体步骤如下： 1. 使用哈希表 map_fre 统计数组 nums 中每个元素出现的频率。 2. 创建一个小顶堆 pri_que，遍历哈希表中的键值对，将 (频率, 元素) 二元组插入堆中。 3. 在插入过程中，如果堆的大小超过 k，则弹出堆顶元素，保证堆中始终维护前 k 个高频元素。 4. 遍历完哈希表后，堆中剩下的就是前 k 个高频元素，将它们按照频率从高到低的顺序弹出并存入结果数组中。 5. 返回结果数组。
时间复杂度: O(n log k)
空间复杂度: O(n)
```python
import heapq
from collections import defaultdict
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# 使用哈希表统计每个元素出现的频率
map_fre = defaultdict(int)
for num in nums:
map_fre[num] += 1
# 创建小顶堆，维护前 k 个高频元素
pri_que = []
for key, freq in map_fre.items():
heapq.heappush(pri_que, (freq, key))
if len(pri_que) > k:
heapq.heappop(pri_que)
# 从堆中弹出前 k 个高频元素，按照频率从高到低的顺序存入结果数组
result = [0] * k
for i in range(k - 1, -1, -1):
result[i] = heapq.heappop(pri_que)[1]
return result
```
如果数组`nums`中的所有元素都相同，那么哈希表`map_fre`中将只有一个键值对，即这个重复元素及其总出现次数。因此，哈希表的大小为1，而不是`n`。
在Python中的小顶堆（使用`heapq`），当元素的第一关键字（在本例中是频率）相同时，它会使用元素的第二关键字进行比较（在本例中是元素本身）。因此，若频率相同，小顶堆会根据元素值大小进行排序。这种方式确实支持在频率相同的情况下，根据元素值的顺序来决定谁先被弹出。不过，这并不会影响题目的解决方法，因为题目只关心频率高低，对于频率相同的元素，并未要求特定的排序顺序。
由于小顶堆`pri_que`维护的是前`k`高频元素，并且堆顶是这些元素中频率最低的，故在将元素从堆中移除并存入结果数组`result`时，需要逆序填充。这是因为堆弹出的顺序是从频率最低到最高，而题目要求是频率从高到低。因此，通过从结果数组的最后一个位置向前填充，可以确保最终数组的顺序与题目要求的前`k`高频的顺序一致。