前k个高频元素(小顶堆实现)

前k个高频元素(小顶堆实现)

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

• 1 <= nums.length <= 105

• k 的取值范围是 [1, 数组中不相同的元素的个数]

• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

解题思路

这道题要求我们在一个整数数组 nums 中找到出现频率前 k 高的元素。可以使用哈希表和小顶堆结合的方式来高效解决。以下是详细的解题思路和每个步骤的解释：

代码实现

以下是完整的代码实现，带有详细的注释：

class Solution {
public:
    // 自定义比较器类，使 priority_queue 变为小顶堆
    class mycomparison {
    public:
        // 重载 operator() 使其按频率排序
        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) {
        // 1. 使用 unordered_map 统计每个元素的频率
        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }

        // 2. 使用小顶堆按频率进行排序，堆大小保持为 k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
        for (auto it = map.begin(); it != map.end(); ++it) {
            pri_que.push(*it);
            // 当堆的大小超过 k 时，弹出堆顶的频率最小元素
            if (pri_que.size() > k) {
                pri_que.pop();
            }
        }

        // 3. 提取结果，将小顶堆中频率前 k 高的元素倒序存入 result 数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; --i) {
            result[i] = pri_que.top().first;//first是key(数组元素)，second是value(出现次数)
            pri_que.pop();
        }

        return result;
    }
};

代码分析

operator() 运算符重载

在 mycomparison 类中重载 () 运算符，使其成为比较器类的核心部分：

bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
    return lhs.second > rhs.second;
}

当 priority_queue 比较两个 pair<int, int> 元素时，会调用 operator()，以频率（second）为标准，从而将频率较小的元素排在堆顶。

unordered_map 的使用

unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
    map[nums[i]]++;
}

unordered_map 用于统计每个元素的频率。因为 unordered_map 使用哈希表实现，能在常数时间内完成插入和查找操作。

小顶堆的定义

priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

• 通过 mycomparison 定义的小顶堆会根据频率大小进行排序，频率较小的元素在堆顶。
• 在遍历哈希表时，小顶堆的大小超过 k 时会删除频率最小的元素，从而保留频率最高的 k 个元素。

参考资料: