347 前k个高频元素

步骤1：统计元素频率

使用哈希表（unordered_map）统计每个元素的出现次数，时间复杂度为 O(n)。

步骤2：构建最小堆维护Top K

• 优先队列（最小堆）：用priority_queue维护当前频率最高的k个元素。
• 堆的排序依据：根据元素的频率排序，堆顶是当前堆中频率最小的元素。
• 操作逻辑：遍历哈希表，将元素插入堆中，若堆大小超过k则弹出堆顶元素，确保堆中始终保留频率最高的k个元素。时间复杂度为 O(n log k)

步骤3：提取结果

将堆中的元素取出，存入结果数组。由于堆顶是频率最小的元素，最终结果无需反转顺序（题目允许任意顺序

关键点解析

1. 哈希表统计频率：遍历数组一次，统计每个元素的出现次数。
    
2. 最小堆优化时间复杂度：维护大小为k的堆，避免对所有元素排序，时间复杂度从O(n log n)优化到O(n log k) 。
    
3. 优先队列的比较方式：使用greater<pair<int, int>>定义最小堆，按频率升序排列，堆顶始终是当前最小的频率值。

复杂度分析

• 时间复杂度：O(n log k)，其中统计频率O(n)，堆操作O(n log k)。
• 空间复杂度：O(n)，哈希表存储所有元素的频率，堆最多存储k个元素。

#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 1. 统计频率
        unordered_map<int, int> freq;
        for (int num : nums) {
            freq[num]++;
        }
        
        // 2. 构建最小堆筛选Top K
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        // 引用 零拷贝
        for (auto& [num, count] : freq) {
            pq.push({count, num});
            if (pq.size() > k) {
                pq.pop();
            }
        }
        
        // 3. 提取结果
        vector<int> res;
        while (!pq.empty()) {
            res.push_back(pq.top().second);
            pq.pop();
        }
        return res;
    }
};

个