描述
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
- 输入: nums = [1,1,1,2,2,3], k = 2
- 输出: [1,2]
示例 2:
- 输入: nums = [1], k = 1
- 输出: [1]
提示：
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 $O(n \log n)$ , n 是数组的大小。
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。
题解
这道题给了我们一个数组，让统计前k个高频的数字，那么对于这类的统计数字的问题，首先应该考虑用 HashMap 来做，建立数字和其出现次数的映射，然后再按照出现次数进行排序。可以用堆排序来做，使用一个最大堆来按照映射次数从大到小排列，在 C++ 中使用 priority_queue 来实现，默认是最大堆。
C++
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> m; // 建立哈希表
// 大根堆
priority_queue<pair<int, int> > q; //pair的比较，先比较第一个元素，第一个相等比较第二个
vector<int> res; // 保存结果
for(auto num: nums) // 将nums元素进行统计后保存至哈希表
m[num]++;
for(auto it: m) // 导入大根堆
q.push({it.second, it.first}); // {value, key}
for(int i=0; i<k; i++){
res.push_back(q.top().second);
q.pop();
}
return res;
}
};Python
字典中get()的用法
Python字典的 get() 方法用于返回指定键的值，如果键不在字典中则返回默认值。它的语法如下：
dictionary.get(key, default=None)其中，key 为字典中要查找的键；default 为键不存在时返回的默认值，如果未提供默认值则返回 None。
举个例子，假设有一个字典 my_dict，其中包含一些键值对：
my_dict = {"apple": 3, "banana": 6, "orange": 9}若要获取 my_dict 中键为 “apple” 的值，可以使用 get() 方法：
value = my_dict.get("apple")
print(value) # 输出 3如果想获取的键不存在于字典中，可以设置默认值：
value = my_dict.get("pear", 0)
print(value) # 输出 0如果不设置默认值，则返回 None：
value = my_dict.get("pear")
print(value) # 输出 None需要注意的是，get() 方法并不会修改字典，如果要修改字典中的值，需要使用赋值语句，例如：
my_dict["apple"] = 5 # 将 "apple" 的值从 3 改为 5代码
Python中也有类似于C++的priority_queue的数据结构，即 heapq 模块提供的堆（heap）。
堆（heap）是一种特殊的树形数据结构，满足堆的性质：对于每个节点 x，其父节点的键值不大于（或不小于）其子节点的键值，且堆中每个节点所存储的值都必须是可比较的。
Python的 heapq 模块提供了一些函数和数据结构，可以方便地实现堆，包括以下函数：
heapq.heappush(heap, item)：将item元素加入到heap中，并保持堆的性质。heapq.heappop(heap)：弹出并返回heap中最小的元素，并保持堆的性质。heapq.heappushpop(heap, item)：先将item元素加入到heap中，然后再弹出并返回heap中最小的元素，并保持堆的性质。heapq.heapify(x)：将列表x转化为一个堆，时间复杂度为 O(n)。heapq.nlargest(n, iterable, key=None)：返回iterable中最大的n个元素。heapq.nsmallest(n, iterable, key=None)：返回iterable中最小的n个元素。
下面是一个使用 heapq 模块实现堆的例子，该例子实现了一个最小堆，并用于获取列表中的前 k 大元素：
import heapq
def find_top_k(nums, k):
# 将 nums 转换为最小堆
heap = [-num for num in nums]
heapq.heapify(heap)
# 取出堆中最小的 k 个元素
top_k = []
for i in range(k):
top_k.append(-heapq.heappop(heap))
return top_k
nums = [1, 3, 5, 2, 4]
k = 3
top_k = find_top_k(nums, k)
print(top_k) # 输出 [5, 4, 3]需要注意的是，Python的堆默认是最小堆，如果需要实现最大堆，可以将元素取相反数再加入堆中，弹出元素时再将其取相反数即可。
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# 要统计元素出现频率
map_ = {}
for i in range(len(nums)):
map_[nums[i]] = map_.get(nums[i], 0) + 1 # 有key加一，无key置零加一
# 对频率排序
# 定一个小根堆，大小为k
pri_que = []
# 用固定大小为k的小顶堆，扫描所有频率的数值
for key, freq in map_.items():
heapq.heappush(pri_que, (freq, key))
if len(pri_que) > k: # 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为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
