[LeetCode]Top K Frequent Words

题目要求log(n * k)的解法，我们先扫一遍array用map记录每一个单词的出现数量，之后用priority queue统计top k即可，保证priority queue的size小于等于k。代码如下：

	class Solution {
	public:
	vector<string> topKFrequent(vector<string>& words, int k) {
	int len = words.size();
	unordered_map<string, int> count;
	auto comp = [](const pair<int, string>& p1, const pair<int, string>& p2){ return p1.first == p2.first? p1.second < p2.second: p1.first > p2.first; };
	priority_queue<pair<int, string>, vector<pair<int, string>>, decltype(comp)> pq(comp);
	for(auto&& word : words)
	++count[word];
	for(auto&& p : count)
	{
	pq.push({p.second, p.first});
	if(pq.size() > k)pq.pop();
	}
	vector<string> res;
	while(pq.size())
	{
	res.push_back(pq.top().second);
	pq.pop();
	}
	reverse(res.begin(), res.end());
	return res;
	}
	};

view raw Top K Frequent Words.cpp hosted with ❤ by GitHub