LeetCode #347：Top K Frequent Elements(前K个高频元素)

题目描述

本题的思路不难，先用 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; // 与快排相反，堆这边大于号(>)是从小到大排列/小顶堆，小于号(<)是从大到小排列/大顶堆
        }
    };
};