本题的思路不难,先用 map 统计各个元素出现的频率,再用小顶堆(或大顶堆)找出频率前 k 的元素。在实现的过程中会涉及到对 C++ map、priority_queue、pair 等 STL 库的用法,之前对这块知识有些遗忘,特此记录。
class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> m; // 用map统计每个元素的出现频率 for(int i = 0; i < nums.size(); i ++) { m[nums[i]] ++; } priority_queue<pair<int, int>, vector<pair<int, int>>, Cmp> q; // 创建小顶堆(第二个参数指定堆底层实现的容器,第三个参数不写Cmp函数默认大顶堆) // 用迭代器遍历每一个map中的节点 for(auto it = m.begin(); it != m.end(); it ++) { q.push(*it); if(q.size() > k) { // 当小顶堆中的元素大于k时,弹出元素,确保最后留下的元素是频率前k高的 q.pop(); } } vector<int> res(k); for(int i = k - 1; i >= 0; i --) { // 倒序将答案放入结果数组 res[i] = q.top().first; // first是pair的前一个元素,second是后一个元素 q.pop(); } return res; } private: // 堆的比较函数 class Cmp { public: bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) { return lhs.second > rhs.second; // 与快排相反,堆这边大于号(>)是从小到大排列/小顶堆,小于号(<)是从大到小排列/大顶堆 } }; };