Top K高频单词问题：如何按频率降序及字典序返回结果

给定字符串数组words和整数k，返回出现频率前k高的字符串。结果需按频率从高到低排序；频率相同的单词按字典序排序。

示例1 #

输入: words = ["i","love","leetcode","i","love","coding"], k = 2
输出: ["i","love"]
解释: "i"和"love"是出现频率最高的两个单词，因"i"字典序更小，故排在前面。

个人求解过程 #

我尝试通过统计单词频率的方法求解该问题，最初打算遍历k次获取高频单词，但没法按要求的字典序返回结果。目前已解决该问题。

修正后的实现代码 #

原代码的核心问题是默认的sort函数排序逻辑不符合题目要求：默认对pair<string, int>排序会先按字符串字典序升序，再按整数升序，这和题目要求的先频率降序、频率相同则字典序升序的规则冲突。以下是修正后的代码：

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        // 用unordered_map统计频率，比map更高效
        unordered_map<string, int> freq;
        for (const auto& word : words) {
            freq[word]++;
        }

        // 把键值对存入vector以便排序
        vector<pair<string, int>> freqPairs;
        for (const auto& p : freq) {
            freqPairs.push_back(p);
        }

        // 自定义排序规则：频率高的在前；频率相同则字典序小的在前
        sort(freqPairs.begin(), freqPairs.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
            if (a.second != b.second) {
                return a.second > b.second;
            }
            return a.first < b.first;
        });

        // 提取前k个结果
        vector<string> ans;
        for (int i = 0; i < k; ++i) {
            ans.push_back(freqPairs[i].first);
        }
        return ans;
    }
};

代码说明 #

• 统计频率阶段使用unordered_map，避免map自带的排序开销，提升效率；
• 排序时通过lambda表达式明确排序规则，优先比较频率（降序），频率相同时比较字符串字典序（升序）；
• 最后直接截取排序后数组的前k个字符串作为结果，符合题目要求。

内容的提问来源于stack exchange，提问作者falling down