算法力扣刷题三十三【347.前 K 个高频元素】

🕗 发布于 2024-07-07 11:14 算法 leetcode 职场和发展 c++ 数据结构

前言

栈和队列篇。
记录三十三【347.前 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 个高频元素的集合是唯一的

进阶：

你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

二、尝试实现

思路一

用哈希法，因为涉及到元素——次数，可以想到map这种结构。
（1）先统计每个元素出现的次数：元素作为key，次数作为value。不需要有序，不允许重复。所以定义一个unordered_map；
（2）再把次数调整为key，元素作为value。因为要对次数排序，操作的是次数，所以key需要改成次数。最好是有序（这样就不用排了），次数可能重复。所以定义一个multimap。
（3）返回结果把multimap内后k个取出来，获取second，得到result。

代码实现一

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        multimap<int,int> s;
        //统计次数
        for(int i = 0;i < nums.size();i++){
            map[nums[i]]++;
        }
        //调整次数为key，元素作为value
        for(auto it = map.begin();it != map.end();++it){
            s.insert(pair<int,int>(it->second,it->first));
        }
        
        vector<int> result;
        auto it = s.end();
        //把multimap的后k个取出来，push_back元素，返回结果。
        while(k--){
            it--;
            result.push_back(it->second);
        }
        return result;
    }
};

时间复杂度：统计次数，遍历nums长度为n；当放到multimap中长度也是n；再找后k个取值的时候，是log(n)。所以O(n log n)。

思路二

记录三十二中有单调队列的使用。这里能不能也自定义单调队列，实现频率前k高的元素维护？
（1）队列用deque容器，放置类型pair<int,int>，对值，first是次数，second是元素。
（2）把nums先排序，再遍历结束之前无法确定频率前k高是谁，只能都暂时保留记录，让单调队列里面次数单调递减。需要一个辅助结构来调整顺序。
（3）需要哪些函数呢？先完成主函数，再补充单调队列功能。（看代码注释）

代码实现二

class Solution {
public:
class Dq{
    deque<pair<int,int>> dq;//想dq中大小是k，只放前k高的频率。
    stack<pair<int,int>> st;//辅助结构
    int size;
public:
    Dq(int k):size(k){}
    void push(pair<int,int> val){
        while(!dq.empty() && val.first > dq.back().first){
            st.push(dq.back());
            dq.pop_back();
        }
        dq.push_back(val);
        this->resizeDQ();
    }
    void resizeDQ(){
        while(dq.size() < size && !st.empty()){    //dq放置前k高频率
            dq.push_back(st.top());
            st.pop();
        }
        return;
    }
    int pop(){//调整为直接返回元素。
        int num = dq.front().second;
        dq.pop_front();
        return num;
    }
};
    vector<int> topKFrequent(vector<int>& nums, int k) {
    //不确定size == 1，边界情况在for循环中包不包含，所以先写上，发现for循环可以包含所以注释掉。
        // if(nums.size() == 1){
        //     return nums;
        // }
        sort(nums.begin(),nums.end());//先排序。重复的肯定紧挨着，可以判断下一个和前一个是否相等
        //遍历nums，找每个元素的出现次数。
        int count = 1; //初始化为1
        Dq que(k);
        for(int i = 1;i < nums.size();i++){
            if(nums[i] != nums[i-1]){
                pair<int,int> p(count,nums[i-1]);
                que.push(p);//统计出来一个元素的出现次数。放入单调队列中
                count = 1;
            }else{
                count++;
            }
        }
        que.push(pair<int,int> (count,nums[nums.size()-1]));//要把最后的也放进去。
   
        vector<int> result;
        while(k--){
            result.push_back(que.pop());//从单调队列中弹出频率前k高的元素。
        }
        return result;
    }
};

三、参考思路

参考思路链接

学习内容

思路：
（1）数据结构：大顶堆和小顶堆。用来在集合里求前k个高频或低频结果。堆底层实现完全二叉树。

大顶堆：父亲始终大于左右两个孩子，所以最高点是最大的值；
小顶堆：父亲始终小于左右两个孩子，所以最高点是最小的值；

（2）如何用堆实现？选大顶堆还是小顶堆？

堆的操作
- 插入元素：先把元素放到堆的末尾，再和父节点比较，进行上浮，调整大小，使得满足大小；
- 删除元素：结果：弹出堆顶元素。先把堆顶元素和最后元素交换，再进行浮动调整；
题目要获得高频前k个，设置堆内只有k个元素，如果放进来一个，那么，pop一个，pop的是堆顶元素，应该把最小的pop出去，留下大的值。所以选择小顶堆。

（3）C++中有没有堆的结构可以直接实现？
#include < queue >中有priority_queue类。（这个类的解释见补充）

代码实现

学习完priority_queue和思路，先尝试按该思路实现。再对比参考注意细节问题。

因为priority_queue的默认比较函数是less，默认构成大顶堆。所以要自定义比较函数。
priority_queue内元素类型是pair<int,int>，first是出现次数，second是元素值。

class Solution {
public:
class Mycmp{
public:
    bool operator() (const pair<int,int>& x,const pair<int,int>& y) const{
        return x.first >= y.first;   //当值越大越是true，排序下来最小的在堆顶
    }
};
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;//统计元素出现的次数
        priority_queue<pair<int,int>,vector<pair<int,int>>,Mycmp> que;
        for(int i = 0;i < nums.size();i++){ //元素值作为key，次数作为value。重新调整。
            map[nums[i]]++;
        }

        for(auto it = map.begin();it != map.end();++it){
            pair<int,int> p(it->second,it->first);//构造pair元素，次数作为比较的对象。
            if(que.size() < k){ //堆内不足k个，直接放入
                que.push(p);
            }else if(que.size() == k){
                que.push(p);
                que.pop();
            }
        }

        //处理堆剩下的元素
        vector<int> result;
        while(!que.empty()){
            result.push_back(que.top().second);
            que.pop();
        }
        return result;
    }
};

对比参考代码，改进之处：

参考在compare函数中直接比较second，不需要再pair<int,int>构造，把map中的值放进来；
放入堆时，if-else if都需要push，统一起来。只if(size > k) 的情况。

总结

本道题用了3种代码实现：
- 第一种：看到统计次数，想能不能用哈希结构？所以先统计次数，再调整key和value，用有序且需要重复的multimap结构排序。最后取出后k个。
- 第二种：实现一个DQ单调队列，为所有出现次数进行排序，维护DQ队列中出现次数递减。应用记录三十二中所学单调队列的方法。
- 第三种：使用堆结构，C++中priority_queue类，构造小顶堆。保持排序的完全二叉树结构。
下面补充priority_queue使用方法：

补充：priority_queue类

概念

优先级队列。

用处：使用堆结构，堆可以用来优先级确定、排序。在< queue >头文件中。
只能top()访问堆顶元素，堆顶元素比其他的都要大。
priority_queue底层实现容器：vector或deque。这个容器能够操作：empty()、size()、front()、push_back()、pop_back()。默认是vector
- 提一下vector：push_back()、pop_back()看起来是vector的尾部（“后端”），但从这个后端pop出priority_queue的堆顶。
为什么始终能保持堆结构呢？因为底层容器支持random access iterator，并且priority_queue可以自动调用make_heap、pop_heap、push_heap算法。

定义

template <class T, 
  class Container = vector<T>, 
  class Compare = less<typename Container::value_type> >
class priority_queue;

解释：

T：队列内元素类型；
Container ：底层实现默认用vector。
Compare：一个比较函数。可以自定义。两个参数类型是T，返回值bool类型。如果a < b，返回true，最后排序是最小到大，priority_queue中pop的是最后一个元素，也就是最大值（大顶堆）。
所以，如果实现小顶堆，需要自定义比较函数，更改方式。默认维护的是大顶堆。
额外：什么是严格弱排序？4条性质，需要自定义函数时检查能否满足下面这4条性质。
- 自身比较：a < a，return false；
- 传递性：a < b,b < c，那么a < c，return true；
- 如果a < b，return true；那么 b < a，return false；
- 不可比较性：如果a,b带进去无法比较，return false,;b,c带进去无法比较，return false;那么a,c带进去也是不可比较。（带进比较函数里）

构造函数

函数原型：类型是定义类时给的。

比较函数Compare在容器结构Container的前面：
原型一：priority_queue (const Compare& comp, const Container& ctnr);
原型二：template <class InputIterator>  priority_queue (InputIterator first, InputIterator last, const Compare& comp, const Container& ctnr); //first和last可以传指针，代表范围。

比如用默认的Container和Compare：
priority_queue<int,vector<int>,less<int>> first; 等同于：priority_queue<int> first;

自定义Container和Compare:
class MyCmp{
public:
bool operator()(int& a,int&b){
return a>b;//改成小顶堆
}
};
priority_queue<int,vector<int>,Mycmp> second;
Mycmp cmp;
priority_queue<int,vector<int>,Mycmp> second(cmp);

成员函数（数量不多）

void empty();//判断空？
size_type size();//大小。元素数量
const_reference top() const;//获取堆顶，返回引用。实际是调用底层的front()
void push (const value_type& val);//放入元素。先调用底层容器的push_back()，再调用push_heap()排序
void push (value_type&& val);
void pop();//移除堆顶。先调用pop_heap函数，再调用底层容器的pop_back()，再调用元素的析构。
void swap (priority_queue& x) noexcept;//交换两个priority_queue的内容和比较函数，同类型的priority_queue，size可以不同。
swap(x，y);//参数x,y是同类型的priority_queue，交换容器的值和比较函数。

总结：empty/size/push/pop/top/swap处理堆内元素。

（欢迎指正，转载表明出处）

原文地址：https://blog.csdn.net/danaaaa/article/details/140208587

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Django QuerySet对象，all()方法
下一篇：接口依赖-动态参数+数据依赖的代码

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

算法力扣刷题 三十三【347.前 K 个高频元素】

前言