题目描述

原题链接：347. 前 K 个高频元素

一、优先队列（小根堆）+Hash表

使用Hash表存nums中各元素出现次数，维护一个优先级队列，在里面存k个数，采用小根堆方式，从小到大进行排列。当存入的数多余k个时，将队头（最小值）弹出。

C++优先队列(priority_queue)用法详解、【C++】小白友好【优先队列的基础知识】

STL 中，priority_queue 容器适配器的定义如下：

template <typename T,
        typename Container=std::vector<T>,
        typename Compare=std::less<T> >
class priority_queue{
    //......
}

默认的构建方式为大根堆：less<>

使用自定义的数据类型的时候，可以重写比较函数，也可以进行运算符重载（less重载小于“<”运算符，构造大根堆；greater重载大于“>”运算符，构造小根堆）。

C++ STL priority_queue容器适配器详解

class Solution {
public:
    class mycomparison {
    public:
        // 小根堆的方式。注：< 为大根堆        
        // rhs初始时，指向新加入元素。
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;            
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // key为nums中的数，value为nums的出现次数
        unordered_map<int, int> record;
        for(int num : nums) {
            record[num]++;            
        }
        // 建立小根堆排列方式的优先队列
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
        for(unordered_map<int, int>::iterator it = record.begin(); it != record.end(); it++) {
            pri_que.push(*it);
            // 插入元素个数k时，弹出当前的最小值
            if(pri_que.size() > k) {
                pri_que.pop();
            }
        }
        vector<int> res(k);
        for(int i = k - 1; i >= 0; i--) {
            res[i] = pri_que.top().first;
            pri_que.pop();
        }
        return res;
    }
};

时间复杂度 $O(nlogk)$（堆中至多k个，每次调整堆需要$O(logk)$）
空间复杂度 $O(n)$

参考文章：
347.前 K 个高频元素、前 K 个高频元素