LeetCode 347. 前K个高频元素（堆排、快排和桶排的应用）

2020年9月2日 周三 天气晴 【不悲叹过去，不荒废现在，不惧怕未来】

---

本文目录

1. 优先级队列（最小堆）2. 快速选择（快排的优化）3. 桶排序

---

LeetCode 347. 前K个高频元素

本题可看作 求前k个最大元素 的拓展，先用哈希表统计出每个元素出现的频率，然后对频率进行排序，求出前k个最大的频率，返回频率对应的值即可。

1. 优先级队列（最小堆）

class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { // 1.用哈希表统计每个数出现的频率 unordered_map<int,int> map; for(auto num:nums) ++map[num]; // 2.对频率进行排序，求前k个最大的频率 priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq; // 最小堆 for(auto it:map){ if(pq.size()==k){ if(pq.top().first<it.second){ pq.pop(); pq.push(make_pair(it.second,it.first)); } } else pq.push(make_pair(it.second,it.first)); } // 3.取出最小堆中的元素 vector<int> res; while(!pq.empty()){ res.emplace_back(pq.top().second); pq.pop(); } return res; } }; 时间复杂度：$O\left(n\log k\right)$ 证明过程：$$\underset{k}{\log 1+\log 2+...+\log k}+\underset{n-k}{\log k+...+\log k}=\log k!+\left(n-k\right)\log k\le \log k^k+\left(n-k\right)\log k=n\log k$$空间复杂度：$O\left(n\right)$

2. 快速选择（快排的优化）

class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { // 1.用哈希表统计每个元素出现的频率，并将元素和对应频率送入vector等待排序 unordered_map<int,int> map; for(auto num:nums) ++map[num]; vector<pair<int,int>> freq; for(auto it:map) freq.emplace_back(make_pair(it.first,it.second)); // 将元素和对应频率送入vector // 2.利用快速选择算法获取频率第k高元素的索引 int len = freq.size(); quickSelect(freq,0,len-1,len-k); // 3.根据频率第k高元素的索引，获取频率前k高的元素 vector<int> res; for(int i=len-k;i<len;++i) res.emplace_back(freq[i].first); return res; } // 基于快排的选择方法（快速选择算法） void quickSelect(vector<pair<int,int>>& nums, int l, int r, int k){ int rand_idx = rand() % (r-l+1) + l; swap(nums[l],nums[rand_idx]); int idx = partition(nums,l,r); if(idx==k) return; else idx<k?quickSelect(nums,idx+1,r,k):quickSelect(nums,l,idx-1,k); } // 分割操作（以中轴元素为基准，将数组分割成三部分，返回中轴元素索引） int partition(vector<pair<int,int>>& nums, int l, int r){ auto pivot = nums[l]; // 取第一个位置的元素作为中轴元素 while(l < r){ // 右边主动接近左边，进行循环覆盖 while(l < r && nums[r].second > pivot.second) --r; nums[l] = nums[r]; while(l < r && nums[l].second <= pivot.second) ++l; nums[r] = nums[l]; } // 把pivot交换到中间，完成分割（因为是右边主动接近左边，所以这里是nums[l]） nums[l] = pivot; return l; } }; 时间复杂度：由于引入了随机化，时间代价的期望是$O\left(n\right)$空间复杂度：$O\left(n\right)$

3. 桶排序

class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { // 1.用哈希表统计每个元素出现的频率 unordered_map<int,int> map; for(auto num:nums) ++map[num]; // 2.建立大小为len+1的桶，i位置存放频率为i的元素 int len = nums.size(); vector<vector<int>> buckets(len+1); for(auto it:map) buckets[it.second].emplace_back(it.first); // 3.按频率从高到低输出k个元素到结果数组中 vector<int> res; for(int i=len;i>=0;--i){ for(auto it:buckets[i]){ res.emplace_back(it); if(--k==0) return res; } } return res; } }; 时间复杂度：$O\left(n\right)$空间复杂度：$O\left(n\right)$