前缀树]leetcode692:前K个高频单词(medium)"/>
[前缀树]leetcode692:前K个高频单词(medium)
题目:
题解:
使用map代替前缀树,若手动实现前缀树感觉费力不讨好,最后还是要将<string, int>装到vector进行排序,所以直接用map就好啦。
代码如下:
class Solution {
public://题解:用map代替前缀树vector<string> topKFrequent_1(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]++;}//由于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;}
};
更多推荐
[前缀树]leetcode692:前K个高频单词(medium)
发布评论