前言

栈和队列篇。
记录 三十三【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;
    }
};

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

1. 参考在compare函数中直接比较second，不需要再pair<int,int>构造，把map中的值放进来；
2. 放入堆时，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处理堆内元素。

---

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