栈和队列：找到前K个高频元素和队列有什么关系？ ？

由于整数字段非空，返回出现频率最高的元素。

示例 1：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]

示例 2：‶ : nums = [1], k = 1
输出：[1]

提示：
您可以假设给定的 k 始终是合理的，并且对于数组 number 中的不同元素，1 ≤ k ≤ 。
算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。
问题数据确保答案是唯一的。换句话说，数组中前 k 个高频元素的集合是唯一的。
您可以按任何顺序返回答案。 ？频率，这类问题可以使用地图来计算。

那么我们这里可以使用一个容器适配器来进行频率排序，也就是“优先级队列”。

什么是优先级队列？

事实上“它只是一个被队列覆盖的堆”因为优先级队列外接口只从队列头部取出元素，并从队列尾部添加元素。没有其他方法可以获取元素。看起来只是一个队列。

并且优先级队列中的元素会根据元素的权重自动排序。那么它是如何组织的呢？

默认情况下，队列优先级使用max-heap（大上堆）来完成元素排序。这个大顶堆就是一棵用向量形式表示的完全二叉树（Complete Binary Tree）。

什么是堆？

“堆是一棵完全二叉树。树中每个节点的值不小于（或大于）其左右子节点的值。” 如果父节点大于等于左右子节点，则为大顶堆，小于等于左右子节点为小顶堆。

所以大家经常讲大顶堆（堆头是最大的元素）和小顶堆（堆头是最小的元素）。如果懒得自己实现，就用priority_queue（优先级队列）。底层设计是一样的。从小到大的行是小的顶部堆栈，从大到小的行是大的顶部堆栈。

在这个问题中我们将使用优先级队列来对一些频率进行排序。

为什么不使用快速排序呢？要使用快速排序，必须将映射转换为向量结构，然后对整个数组进行排序。在这种情况下，我们实际上只需要维护 k 个有序序列，因此使用优先级队列是最佳选择。

这时，你就要想，到底该用小顶盘还是大顶盘呢？

有同学认为这道题需要前K个高频元素，所以肯定使用大上栈。

那么问题是定义一个大小为k的大顶堆，每次更新大顶堆时，每次都会弹出最大的元素，那么如何保存前K个高频元素呢？元素呢。

“所以我们必须使用小顶堆，因为我们需要统计从顶到最大的元素。只有小顶堆每次都会推出最小的元素，最终从顶到最大的元素是收集到小顶堆中。”

求第一个到最大元素的流程如图所示：（图中只有三个频率，所以只形成大小为3的小上堆，如果频率较大，就用这个小堆上堆扫描）

我们看一下代码：

C++代码

// 时间复杂度：O(nlogk)
// 空间复杂度：O(n)
class Solution {
public:
    // 小顶堆
    class mycomparison {
    public:
        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) {
        // 要统计元素出现频率
        unordered_map<int, int> map; // map<nums[i],对应出现的次数>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }

        // 对频率排序
        // 定义一个小顶堆，大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
        
        // 用固定大小为k的小顶堆，扫面所有频率的数值 
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
        }

        // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒叙来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;

    }
};