一、解题思路统计频率使用 mapstring, int 统计每个单词出现的次数map 会自动根据键单词进行字典序升序排列这一步为后续同频次单词的排序奠定了基础转存到 vector将 map 中的键值对pairstring,int存入 vector以便使用 STL 排序算法按频率降序排序使用 stable_sort 配合自定义仿函数按频率降序排列为什么用 stable_sort因为 stable_sort 是稳定排序不会改变相等元素的相对顺序而 map 中原本已经按照字典序排好了相同频率的单词稳定排序后这些单词的字典序顺序将被保留如果使用 sort不稳定排序相同频率的单词顺序可能被改变需要额外处理字典序提取前 k 个单词将排序后 vector 的前 k 个元素的 first单词存入结果数组并返回二、代码实现附详细注释classSolution{//创建一个仿函数用于根据单词出现频次比较大小辅助stable_sort根据频次降序排序structCompare{booloperator()(constpairstring,inta,constpairstring,intb){returna.secondb.second;}};public:vectorstringtopKFrequent(vectorstringwords,intk){//map的作用//1.根据key值string类型把单词排序map默认对string类型的key值进行字典序排序//这样下来提前根据字典序排好当出现频次相同的单词时就不必再根据字典序进行二次排序//因为map提前已经给你排好字典序了//2.把每个不同的单词出现的频次记录下来方便后面对频次不同的单词进行频次降序排序mapstring,intmapCount;for(autoch:words){mapCount[ch];}//把已经排好字典序的pair值放进vector数组方便stable_sort排序的时候使用vectorpairstring,intv(mapCount.begin(),mapCount.end());//把存有pair值的vector数组元素进行比较使用stable_sort排序的原因是//该排序稳定性好不会打乱相同频次单词之间事先用map排好的字典序stable_sort(v.begin(),v.end(),Compare());//把符合题目排序要求的数组的前K个pair元素的key值放入新的vector数组用与返回vectorstringvwords;for(inti0;ik;i){vwords.push_back(v[i].first);}returnvwords;}};三、关键点解析为什么用 map 而不是 unordered_mapunordered_map 哈希表统计频率更快O(1) 平均但不会对键排序若使用 unordered_map后续排序时同频次单词需要额外进行字典序排序代码会复杂一些本题数据规模适中map 的 O(n log n) 插入足够高效且简洁stable_sort 的作用假设有两个单词 “apple” 和 “banana” 都出现 2 次在 map 中顺序为 “apple” 先于 “banana”不稳定排序可能交换它们的顺序导致结果字典序错误stable_sort 保证相同频率的单词保持原来的相对顺序即保持字典序仿函数 Compare 的设计重载 operator() 返回 a.second b.second实现降序也可以直接使用 lambda 表达式但仿函数使代码更清晰时间复杂度统计频率O(n log n)插入 map排序O(m log m)m 为不同单词个数m ≤ n四、测试