Medium

题目描述

给定一个单词数组 words 和一个整数 k，返回前 k 个高频单词。

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

示例 1：

输入: words = ["i","love","leetcode","i","love","coding"], k = 2
输出: ["i","love"]
解释: "i" 和 "love" 为出现次数最多的两个单词，均出现2次。
注意，按字母顺序 "i" 在 "love" 之前。

示例 2：

输入: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
输出: ["the","is","sunny","day"]
解释: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。

提示：

  • 1 <= words.length <= 500
  • 1 <= words[i].length <= 10
  • words[i] 仅由小写英文字母组成
  • k 的取值范围是 [1, 该数组中不同单词的个数]

进阶： 尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

解题思路

这道题要求找出前K个高频单词，并且相同频率的单词要按字典序排列。有几种解法思路：

方法一：哈希表 + 排序（推荐）

  1. 使用哈希表统计每个单词的频率
  2. 将所有单词按照题目要求排序：先按频率降序，频率相同时按字典序升序
  3. 取前K个单词

这种方法简单直观，代码易理解，时间复杂度为O(n log n)。

方法二：哈希表 + 最小堆

  1. 使用哈希表统计频率
  2. 维护一个大小为K的最小堆，堆顶是频率最小的元素
  3. 遍历哈希表，如果堆大小小于K就直接加入，否则与堆顶比较决定是否替换
  4. 最后将堆中元素按要求排序

这种方法能达到O(n log k)的时间复杂度，适合K很小的情况。

方法三：桶排序

利用频率作为桶的索引，相同频率的单词放在同一个桶中并排序，最后从高频率桶开始收集结果。

考虑到代码简洁性和通用性，推荐使用方法一。

代码实现

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> freq;
        for (const string& word : words) {
            freq[word]++;
        }
        
        vector<string> candidates;
        for (const auto& p : freq) {
            candidates.push_back(p.first);
        }
        
        sort(candidates.begin(), candidates.end(), [&](const string& a, const string& b) {
            if (freq[a] != freq[b]) {
                return freq[a] > freq[b];
            }
            return a < b;
        });
        
        return vector<string>(candidates.begin(), candidates.begin() + k);
    }
};

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        from collections import Counter
        
        freq = Counter(words)
        
        candidates = list(freq.keys())
        candidates.sort(key=lambda word: (-freq[word], word))
        
        return candidates[:k]

public class Solution {
    public IList<string> TopKFrequent(string[] words, int k) {
        var freq = new Dictionary<string, int>();
        foreach (string word in words) {
            freq[word] = freq.GetValueOrDefault(word, 0) + 1;
        }
        
        var candidates = freq.Keys.ToList();
        candidates.Sort((a, b) => {
            int freqCompare = freq[b].CompareTo(freq[a]);
            return freqCompare != 0 ? freqCompare : a.CompareTo(b);
        });
        
        return candidates.Take(k).ToList();
    }
}

var topKFrequent = function(words, k) {
    const freq = new Map();
    for (const word of words) {
        freq.set(word, (freq.get(word) || 0) + 1);
    }
    
    const candidates = Array.from(freq.keys());
    candidates.sort((a, b) => {
        if (freq.get(a) !== freq.get(b)) {
            return freq.get(b) - freq.get(a);
        }
        return a.localeCompare(b);
    });
    
    return candidates.slice(0, k);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
哈希表 + 排序O(n log n)O(n)
哈希表 + 最小堆O(n log k)O(n)
桶排序O(n)O(n)

其中 n 是单词总数。推荐解法的时间复杂度为 O(n log n)，空间复杂度为 O(n)。

相关题目