优先队列的实践

小灰灰 2024-03-31 10:41 59阅读 0赞

#### 一、使用背景 ####

对于前 k 大或前 k 小这类问题，有一个通用的解法：优先队列。优先队列可以在 O(log⁡n) 的时间内完成插入或删除元素的操作（其中 n 为优先队列的大小），并可以 O(1)地查询优先队列顶端元素。

#### 二、[前K个高频单词][K] ####

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

![a07eb74ee87b43e799d62063e484e5de.png][]

#### 三、使用最小堆 ####

我们可以创建一个最小堆的优先队列（顾名思义，顶端元素是最小元素的优先队列）。我们将每一个字符串插入到优先队列中，如果优先队列的大小超过了 k，那么我们就将优先队列顶端元素弹出。这样最终优先队列中剩下的 k 个元素就是前 k 个出现次数最多的单词。

class Solution {
    public:
    	struct  MyCompare {
    		bool operator()(const pair<string, int>& p1, const pair<string, int>& p2) {
    			//词频由高到低排序：最小堆；字母顺序排序：最大堆
    			return p1.second == p2.second ? (p1.first < p2.first) : p1.second > p2.second;
    		}
    	};
    
    	vector<string> topKFrequent(vector<string>& words, int k) {
    		//使用map统计单词的频度
    		map<string, int> counts;
    		for (string str : words) {
    			counts[str] += 1;
    		}
    
    		//创建小根堆：使用仿函数，注意这里不能写成 minHeap(MyCompare)
    		priority_queue<pair<string, int>, vector<pair<string, int>>, MyCompare> minHeap;
    		//维护大小为k的小根堆
    		//遍历map容器，向小根堆插入对组元素
    		for (auto &it : counts) {
                minHeap.push(it);
                if (minHeap.size() > k) {
                    minHeap.pop();
                }
            }
    
    		//遍历完成后，存储最小堆的元素：堆顶元素的频度最低
    		//倒序接收数据
    		vector<string> res(k);
    		while (k-- > 0) {
    			res[k] = minHeap.top().first;
    			minHeap.pop();
    		}
    		return res;
    	}
    };

#### 四、使用大顶堆 ####

直接将频率最高的元素入队，最后选择前面k个元素存入到vector中

class Solution {
    public:
        vector<string> topKFrequent(vector<string>& words, int k) {
    
            if (words.empty() || k == 0) {
                return {};
            }
            map<string, int> record_1;  // 单词->该单词出现的个数
            vector<string> result;
            for (const auto &word : words) {
                record_1[word]++;
            }
    
            auto cmp = [](const pair<string, int> &a, const pair<string, int> &b) {
                if (a.second != b.second) {
                    return a.second < b.second;
                } else {
                    return a.first > b.first;  //  次数相同，比较字典序列
                }};
    
                // 频率最高的K个
                // 使用最大堆
                priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> que(cmp);
    
                for (const auto &word : record_1) {
                    que.push(word);
                }
    
                // 将vector的前k个元素添加到result中
                while (!que.empty()) {
                    if (k-- == 0)
                        break;
                    result.push_back(que.top().first);
                    que.pop();
                }
                return result;
        }
    };

#### 五、sort排序法 ####

class Solution {
    public:
        vector<string> topKFrequent(vector<string>& words, int k) {
            unordered_map<string, int> cnt;
            for (auto& word : words) {
                ++cnt[word];
            }
            vector<string> rec;
            for (auto& [key, value] : cnt) {
                rec.emplace_back(key);
            }
            sort(rec.begin(), rec.end(), [&](const string& a, const string& b) -> bool {
                return cnt[a] == cnt[b] ? a < b : cnt[a] > cnt[b];
            });
            rec.erase(rec.begin() + k, rec.end());
            return rec;
        }
    };

或者

class Solution {
    public:
    	//题解：用map代替前缀树
    	vector<string> topKFrequent(vector<string>& words, int k) {
    		if (words.empty() || k == 0)return {};
    		unordered_map<string, int> record_1; //单词->该单词出现的个数
    		vector<string> result;
    		for (const auto& word : words) {
    			record_1[word]++;
    		}
    		//由于map不支持value的sort排序，所以必须将map转换为vector才能进行sort自定义排序
    		vector<pair<string, int>> record_2(record_1.begin(), record_1.end());
    
    		//sort的第三个参数是lambda表达式，其实和传普通函数一样，sort的第三个参数是支持二元谓词的
    		sort(record_2.begin(), record_2.end(),
    			[](const pair<string, int>& a, const pair<string, int>& b){
    			if (a.second == b.second) {
    				return a.first < b.first;
    			}
    			else {
    				return a.second > b.second;
    			} 
    		});
    
    		//将vector的前k个元素添加到result中
    		for (const auto& r : record_2)
    		{
    			if (k-- == 0)break;
    			result.push_back(r.first);
    		}
    		return result;
    	}
    };

参考：

[力扣][Link 1]

[K]: https://leetcode.cn/problems/top-k-frequent-words/
[a07eb74ee87b43e799d62063e484e5de.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/efae9b761b7a4a0da934f1ae473a1b9c.png
[Link 1]: https://leetcode.cn/problems/top-k-frequent-words/submissions/