347. 前 K 个高频元素

题目：

思考：

1. 使用堆实现
2. 如果采用把数组所有元素建立成大根堆然后执行k次输出根后调整的话复杂度就是nlogn会超时，且不符合要求
3. 采用大小只有k的小根堆
4. 遇到比小根堆更大的元素就替换小根堆的根，并进行调整
5. 最后剩下的k个元素就是最大的k个元素
6. 在本题中大小指代出现的频率
7. 难点在于
   1. 获取频率
   2. 初始化和调整堆

实现：

class Solution {
public:vector<pair<int,int>> tree;int size=0;
public:vector<int> topKFrequent(vector<int>& nums, int k) {vector<int> ret;vector<pair<int,int>> number_fre;for (auto n:nums){bool find_n=false;for (auto& p:number_fre){if (p.first==n){p.second++;find_n=true;break;}}if (!find_n){number_fre.push_back(make_pair(n,1));}}init(number_fre,k);for (int i=k;i<number_fre.size();i++){if (number_fre[i].second>tree[0].second){tree[0]=number_fre[i];adjustTree(0);}}for (auto p:tree){ret.push_back(p.first);}return ret;}void init(vector<pair<int,int>> number_fre,int k ){for (int i=0;i<k;i++){tree.push_back(number_fre[i]);size++;}buildTree();}void buildTree(){int max=size/2-1;while(max>-1){adjustTree(max);max--;}}void adjustTree(int pos){while(2*pos+1<size){int left=2*pos+1;int right=2*pos+2;bool has_adjust=false;if (right<size){if (tree[left].second>tree[right].second){if (tree[right].second<tree[pos].second){swap(tree[right],tree[pos]);pos=right;has_adjust=true;// continue;}}   else{if (tree[left].second<tree[pos].second){swap(tree[left],tree[pos]);pos=left;has_adjust=true;}}}else{if (tree[left].second<tree[pos].second){swap(tree[left],tree[pos]);pos=left;has_adjust=true;} }if (!has_adjust){break;}}}
};