asp.net 网站强制兼容性运行,如何查询公司名称是否被注册,wap网站生成,贵阳制作前言
栈和队列篇。 记录 三十三【347.前 K 个高频元素】 一、题目阅读
给你一个整数数组 nums 和一个整数 k #xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums [1,1,1,2,2,3], k 2
输出: [1,2]示例 2:
输入: nums [1]…前言
栈和队列篇。 记录 三十三【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:vectorint topKFrequent(vectorint nums, int k) {unordered_mapint,int map;multimapint,int s;//统计次数for(int i 0;i nums.size();i){map[nums[i]];}//调整次数为key元素作为valuefor(auto it map.begin();it ! map.end();it){s.insert(pairint,int(it-second,it-first));}vectorint 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容器放置类型pairint,int对值first是次数second是元素。 2把nums先排序再遍历结束之前无法确定频率前k高是谁只能都暂时保留记录让单调队列里面次数单调递减。需要一个辅助结构来调整顺序。 3需要哪些函数呢先完成主函数再补充单调队列功能。看代码注释
代码实现二
class Solution {
public:
class Dq{dequepairint,int dq;//想dq中大小是k只放前k高的频率。stackpairint,int st;//辅助结构int size;
public:Dq(int k):size(k){}void push(pairint,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;}
};vectorint topKFrequent(vectorint nums, int k) {//不确定size 1边界情况在for循环中包不包含所以先写上发现for循环可以包含所以注释掉。// if(nums.size() 1){ // return nums;// }sort(nums.begin(),nums.end()); //先排序。重复的肯定紧挨着可以判断下一个和前一个是否相等//遍历nums找每个元素的出现次数。int count 1; //初始化为1Dq que(k); for(int i 1;i nums.size();i){if(nums[i] ! nums[i-1]){pairint,int p(count,nums[i-1]); que.push(p); //统计出来一个元素的出现次数。放入单调队列中count 1;}else{count;}}que.push(pairint,int (count,nums[nums.size()-1])); //要把最后的也放进去。vectorint result;while(k--){result.push_back(que.pop()); //从单调队列中弹出频率前k高的元素。}return result;}
};三、参考思路
参考思路链接
学习内容
思路 1数据结构大顶堆和小顶堆。用来在集合里求前k个高频或低频结果。堆底层实现完全二叉树。
大顶堆父亲始终大于左右两个孩子所以最高点是最大的值小顶堆父亲始终小于左右两个孩子所以最高点是最小的值
2如何用堆实现选大顶堆还是小顶堆
堆的操作 插入元素先把元素放到堆的末尾再和父节点比较进行上浮调整大小使得满足大小删除元素结果弹出堆顶元素。先把堆顶元素和最后元素交换再进行浮动调整 题目要获得高频前k个设置堆内只有k个元素如果放进来一个那么pop一个pop的是堆顶元素应该把最小的pop出去留下大的值。所以选择小顶堆。
3C中有没有堆的结构可以直接实现 #include queue 中有priority_queue类。这个类的解释见补充
代码实现
学习完priority_queue和思路先尝试按该思路实现。再对比参考注意细节问题。
因为priority_queue的默认比较函数是less默认构成大顶堆。所以要自定义比较函数。priority_queue内元素类型是pairint,intfirst是出现次数second是元素值。
class Solution {
public:
class Mycmp{
public:bool operator() (const pairint,int x,const pairint,int y) const{return x.first y.first; //当值越大越是true排序下来最小的在堆顶}
};vectorint topKFrequent(vectorint nums, int k) {unordered_mapint,int map;//统计元素出现的次数priority_queuepairint,int,vectorpairint,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){pairint,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();}}//处理堆剩下的元素vectorint result;while(!que.empty()){result.push_back(que.top().second);que.pop();}return result;}
};对比参考代码改进之处
参考在compare函数中直接比较second不需要再pairint,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 提一下vectorpush_back()、pop_back()看起来是vector的尾部“后端”但从这个后端pop出priority_queue的堆顶。 为什么始终能保持堆结构呢因为底层容器支持random access iterator并且priority_queue可以自动调用make_heap、pop_heap、push_heap算法。
定义
template class T, class Container vectorT, class Compare lesstypename Container::value_type
class priority_queue;解释
T队列内元素类型Container 底层实现默认用vector。Compare一个比较函数。可以自定义。两个参数类型是T返回值bool类型。如果a b返回true最后排序是最小到大priority_queue中pop的是最后一个元素也就是最大值大顶堆。所以如果实现小顶堆需要自定义比较函数更改方式。默认维护的是大顶堆。额外什么是严格弱排序4条性质需要自定义函数时检查能否满足下面这4条性质。 自身比较a areturn false传递性a b,b c那么a creturn true如果a breturn true那么 b areturn 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_queueint,vectorint,lessint first; 等同于priority_queueint first;自定义Container和Compare:
class MyCmp{
public:bool operator()(int a,intb){return ab; //改成小顶堆}
};
priority_queueint,vectorint,Mycmp second;
Mycmp cmp;
priority_queueint,vectorint,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_queuesize可以不同。
swap(xy);//参数x,y是同类型的priority_queue交换容器的值和比较函数。总结empty/size/push/pop/top/swap处理堆内元素。 欢迎指正转载表明出处
