https://leetcode.cn/problems/top-k-frequent-elements/description/

<aside> 💡

优先级队列：

先使用map存储元素与其出现次数，再将map中的元素存入一个优先级队列中。

• 优先级队列使用小顶堆
  • 队头为最小的元素，随着元素不断加入，队头不断被pop，最后剩下的k个元素就是前K个高频元素
• 时间复杂度：O(nlogk)
  • n：遍历一遍数组
  • logk：每次遍历都调整堆，调整一次堆的时间复杂度为logk（堆是一个二叉树） </aside>

// 用于创建小顶堆的仿函数
// 比较器的定义方式和排序规则有一些差异
// 返回true表示lhs的优先级比rhs低
class MyConmpare {
public:
    bool operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) {
        return lhs.second > rhs.second;
    }
};

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> mp;
    // 先使用哈希表记录个元素的出现频率
    for (int n : nums) {
        mp[n]++;
    }

    // 使用小顶堆存放元素
    // <元素类型, 容器, 比较方法>
    std::priority_queue<std::pair<int, int>, vector<std::pair<int, int>>, MyConmpare> que;

    // 优先级队列仅维护k个元素，低频元素弹出
    for (auto item : mp) {
        que.push(item);
        if (que.size() > k) {
            // 弹出低频元素
            que.pop();
        }
    }

    vector<int> ans(k, 0);
    for (int i = 0; i < k; ++i) {
        ans[i] = que.top().first;
        que.pop();
    }
    
    return ans;
}

感觉哈希表也能做，也是利用map排序的特性，先用一个map统计频率，再将该map的key与value互换，存入另一个map中。从第二个map中取出频率最高的K个元素