给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
示例 2:
? ? ? ? ?本题看到了出现频率、数组，就能想到之前用哈希表map来做的那道题，所以马上盯上哈希表这种方法。首先遍历元素创建一个哈希表，因为此时不知道怎么对哈希表排序，所以又创建了一个容器来装哈希表的value，也就是出现的频率，之后对这个容器进行降序排序，其中用到了greater<int>()，之后遍历k次，每次都让哈去除哈希表里的value和所创建容器的value对比，如果一样并且之前又创建的solu容器没有存放这个结果，那么就将他放入solu中，时间复杂度为两次for循环导致的nk，代码如下：
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> hash; // 定义一个元素和元素数量的哈希表
vector<int> result; // 存放元素数量的容器
for(int i = 0; i < nums.size(); i++)
hash[nums[i]]++;
for(auto i : hash)
result.push_back(i.second);
sort(result.begin(), result.end(), greater<int>()); //将元素数量排序
vector<int> solu;
for(int i = 0; i < k; i++)
{
for(auto it = hash.begin(); it != hash.end(); it++)
{
if(it->second == result[i] && find(solu.begin(),solu.end(),it->first) == solu.end())
{
solu.push_back(it->first);
break;
}
}
}
return solu;
}
};? ? ? ? 之后我发现这段代码可能过于繁琐，就去网上找了一下优化这个代码的方法：前面创建哈希表的部分不变，这时候再创建一个容器vector<pair<int,int>>sortedHash来继承哈希表的元素，但是这个容器由于是个vector，所以是可以通过sort来排序的，在最后一个元素写入一个lambda函数用来让他根据value降序，之后遍历这个sortedHash，直到取到k个结果，完整代码如下：
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> hash; // 定义一个元素和元素数量的哈希表
vector<int> result; // 存放元素数量的容器
for(int i = 0; i < nums.size(); i++)
hash[nums[i]]++;
vector<pair<int, int>> sortedHash(hash.begin(), hash.end());
sort(sortedHash.begin(), sortedHash.end(), [](const auto& a, const auto& b) {
return a.second > b.second;
});
vector<int> solu;
for (const auto& pair : sortedHash)
{
if (solu.size() < k)
{
solu.push_back(pair.first);
}
else break;
}
return solu;
}
};? ? ? ? 但是这个时间复杂度依旧很高，这里采用代码随想录里的方法，优先级队列。缺省情况下priority_queue利用大顶堆完成对元素的排序，这个大顶堆是以vector为表现形式的完全二叉树。因为我们只需要维护前k个元素，所以没有必要用sort里的快速排序，为什么不用大顶堆呢，因为加入元素以后肯定是要pop的，如果用大顶堆，那么pop的就是最大的元素，而我们就要的就是大的，所以本题采用小顶堆，每次将最小的元素弹出，最后小顶堆里积累的就是前k个最大元素。
? ? ? ? 前面遍历创建map没有任何区别，此时创建一个小顶堆priority_queue，这里面有三个参数，一个是队列中元素类型，一个是底层容器的类型，一个是准则。这里尤其不要忘记第二个参数，第三个参数本题采用一个类的形式出现。之后遍历map，每次都将小顶堆里的元素插入进去，一旦超过k了，就将多的那个pop掉。之后再倒序将元素插入到result中，时间复杂度为nlogk，代码如下：
class Solution {
public:
class mycomparision{
public:
bool operator()(const pair<int,int>& a, const pair<int,int>& b)
{return a.second > b.second;}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> map;
for(auto i : nums)
map[i]++;
priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparision> pri_que;
for(auto it = map.begin(); it != map.end(); it++)
{
pri_que.push(*it);
if(pri_que.size() > k)
{
pri_que.pop();
}
}
vector<int> result(k);
for(int i = k-1; i >=0; i--)
{
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};????????
在栈与队列系列中，我们强调栈与队列的基础，也是很多同学容易忽视的点。
使用抽象程度越高的语言，越容易忽视其底层实现，而C++相对来说是比较接近底层的语言。
我们用栈实现队列，用队列实现栈来掌握的栈与队列的基本操作。
接着，通过括号匹配问题、字符串去重问题、逆波兰表达式问题来系统讲解了栈在系统中的应用，以及使用技巧。
通过求滑动窗口最大值，以及前K个高频元素介绍了两种队列：单调队列和优先级队列，这是特殊场景解决问题的利器，是一定要掌握的。
? ? ? ? 解题中二叉树一般有两种主要的形式：满二叉树和完全二叉树。
? ? ? ? 同时还有二叉搜索树，这是一个有数值的树，如果它的左子树不为空，则左子树上所有的节点数值均小于根节点的值，如果右子树不为空，则右子树上所有结点的值均大于根节点的值。它的做右子树也分别为二叉排序树。如果左右两个子树高度差的绝对值不超过1，那么就成为平衡二叉搜索树，也叫ALV树。cpp中的set ，map， multimap，multiset的底层实现都是ALV树，增删操作时间复杂度为logn，而unordered系列底层实现为哈希表。
? ? ? ? 二叉树有顺序存储和链式存储两种方式，如果顺序存储用数组就可以表示。
? ? ? ? 二叉树有两种遍历方式：
? ? ? ? 1、深度优先遍历：先往深走，遇到叶子节点再往回走
? ? ? ? 2、广度优先遍历：一层一层的去遍历
前序遍历：中左右? ?中序遍历：左中右? ? ?后序遍历：左右中
最后写一下二叉树的链式存储定义：
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};