0692. 前K个高频单词【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 哈希表 + 排序

1. 📝 题目描述

• leetcode

给定一个单词列表 words 和一个整数 k，返回前 k 个出现次数最多的单词。

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

---

示例 1：

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

---

示例 2：

输入: ["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, 不同 words[i] 的数量]

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

2. 🎯 s.1 - 哈希表 + 排序

c

typedef struct { char* word; int count; } WordFreq;

int cmp(const void* a, const void* b) {
    const WordFreq* wa = (const WordFreq*)a;
    const WordFreq* wb = (const WordFreq*)b;
    if (wa->count != wb->count) return wb->count - wa->count;
    return strcmp(wa->word, wb->word);
}

char** topKFrequent(char** words, int wordsSize, int k, int* returnSize) {
    // 先排序来分组
    qsort(words, wordsSize, sizeof(char*), (int(*)(const void*,const void*))strcmp);
    WordFreq* wf = (WordFreq*)malloc(sizeof(WordFreq) * wordsSize);
    int n = 0;
    for (int i = 0; i < wordsSize;) {
        int j = i;
        while (j < wordsSize && strcmp(words[i], words[j]) == 0) j++;
        wf[n].word = words[i];
        wf[n].count = j - i;
        n++; i = j;
    }
    qsort(wf, n, sizeof(WordFreq), cmp);
    char** res = (char**)malloc(sizeof(char*) * k);
    for (int i = 0; i < k; i++) res[i] = wf[i].word;
    free(wf);
    *returnSize = k;
    return res;
}

js

/**
 * @param {string[]} words
 * @param {number} k
 * @return {string[]}
 */
var topKFrequent = function (words, k) {
  const freq = new Map()
  for (const w of words) freq.set(w, (freq.get(w) || 0) + 1)
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1] || a[0].localeCompare(b[0]))
    .slice(0, k)
    .map(([w]) => w)
}

py

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        freq = Counter(words)
        return sorted(freq, key=lambda w: (-freq[w], w))[:k]

• 时间复杂度：$O(n\log n)$，其中 n 是单词数量
• 空间复杂度：$O(n)$

算法思路：

• 统计每个单词的出现频率
• 按频率降序、字典序升序排序，取前 k 个