LeetCode刷题——347. 前 K 个高频元素(HOT100)

发布时间:2024年01月17日

???🌈大家好!本篇文章将较详细介绍堆的题目347. 前 K 个高频元素,利用最小堆进行求解。代码语言为:C++代码😇。


347. 前 K 个高频元素

🔒1、题目:

给你一个整数数组 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 个高频元素的集合是唯一的

来源:力扣(LeetCode)👈

??2、思路:

是一棵完全二叉树,树中每个结点的值都不小于(或不大于)其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆小于等于左右孩子就是小顶堆
可以直接用priority_queue(优先级队列)实现,优先级队列的内部是大小顶堆实现的,从小到大排就是小顶堆,从大到小排就是大顶堆。
弹出pop()和队首top()都是获得堆首(根结点)的元素。

  • 具体流程:
  1. 遍历nums数组,哈希表mp记录每个数字出现的次数
  2. 利用优先级队列priority_queue构建小顶堆q,遍历mp,得到代表mp中前k大的数字的数组
  3. 倒序取出前k个频率最大的数存入vector数组

复杂度分析
?时间复杂度::O(nlogk)
🏠空间复杂度:O(n)

🔑3、代码:

	class Solution {
public:
	//两种使用最小堆的方法
    //1.类
    // class mycomparison {
    // public:
    //     bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
    //         return lhs.second > rhs.second;
    //     }
    // };
    //2.函数
    static bool cmp(pair<int,int>&a,pair<int,int>&b){
	        return a.second>b.second;
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> ans(k);
        unordered_map<int,int> mp;
        for(auto num:nums) mp[num]++;//哈希表记录元素出现的次数
        
        //大小为k的小顶堆
        //1.
        //priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_q;
        //2.
        priority_queue<pair<int, int>, vector<pair<int,int>>,decltype(&cmp)>pri_q(cmp); 
        
        // 用固定大小为k的小顶堆,扫面所有频率的数值
        for (auto it = mp.begin(); it != mp.end(); it++) {
            pri_q.push(*it);
            if (pri_q.size() > k) { // 如果堆的大小大于了K,则队列弹出,保证堆的大小一直为k
                pri_q.pop();
            }
        }
        
        //倒序取出前K个频率最大的数
        for(int i = k - 1; i >= 0; i--){
            ans[i]=pri_q.top().first;
            pri_q.pop();
        }
        return ans;
    }
};

文章来源:https://blog.csdn.net/qq_45087381/article/details/135642553
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。