给一非空的单词列表，返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。 输入：第1行为k值，第2行单词列表，单词列表以end结尾，end不属于单词列表中的单词。 2 i love leetcode i love coding end 输出： i love

这是一个经典的算法问题，可以使用哈希表和堆来解决。以下是Python代码实现：

import heapq
from collections import Counter

k = int(input())
words = []
while True:
    word = input()
    if word == 'end':
        break
    words.append(word)

count = Counter(words)
heap = [(-freq, word) for word, freq in count.items()] # 使用堆来获取前k个出现次数最多的单词
heapq.heapify(heap)
top_k = [heapq.heappop(heap) for _ in range(k)]

# 按照要求排序
ans = []
for freq, word in top_k:
    ans.append(word)
ans.sort()

# 输出结果
for word in ans:
    print(word)

输入样例：

2
i love
leetcode
i
love
coding
end

输出样例：

i
love

相关问题

给一非空的单词列表，返回前k个出现次数最多的单词林大oj

题目描述

给一非空的单词列表，返回前k个出现次数最多的单词。

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

示例

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

说明

假定k总为有效值，1 ≤ k ≤ 集合元素数。
输入的单词均由小写字母组成。

解题思路

首先要统计每个单词出现的次数，可以使用哈希表来完成。然后根据出现次数和字母顺序排序，可以使用优先队列来完成。

具体地，将字符串和其出现次数存储到哈希表中，然后将哈希表中的每个元素都加入到优先队列中，队列中元素按照以下规则排序：

- 如果出现次数不同，根据出现次数排序，出现次数多的在前面。
- 如果出现次数相同，根据字母顺序排序，字母靠前的在前面。

最后取出队列前k个元素的字符串即可。

时间复杂度：O(nlogk)。其中n是输入列表的长度，哈希表和优先队列的插入操作的时间复杂度均为O(logk)，总共需要插入n个元素。

空间复杂度：O(n)。哈希表存储n个单词，优先队列存储k个单词。

参考代码

给一非空的单词列表，返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

好的，这道题可以使用哈希表和堆来解决。具体思路如下：

1. 遍历单词列表，统计每个单词出现的次数，记录到哈希表中。
2. 将哈希表中的每个键值对（单词和出现次数）插入到一个大小为k的小根堆中，堆中存储的是出现次数最多的k个单词。
3. 遍历完单词列表后，堆中剩余的就是出现次数最多的k个单词，按照题目要求输出即可。

具体实现可以参考以下C++代码：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
using namespace std;

struct WordFreq {
    string word;
    int freq;
    WordFreq(string w, int f) : word(w), freq(f) {}
    bool operator<(const WordFreq& other) const {
        if (freq == other.freq) {
            return word > other.word;
        }
        return freq < other.freq;
    }
};

vector<string> topKFrequent(vector<string>& words, int k) {
    unordered_map<string, int> freqMap;
    for (string word : words) {
        freqMap[word]++;
    }

    priority_queue<WordFreq> pq;
    for (auto it = freqMap.begin(); it != freqMap.end(); it++) {
        pq.push(WordFreq(it->first, it->second));
        if (pq.size() > k) {
            pq.pop();
        }
    }

    vector<string> result;
    while (!pq.empty()) {
        result.insert(result.begin(), pq.top().word);
        pq.pop();
    }

    return result;
}

int main() {
    vector<string> words = {"i", "love", "leetcode", "i", "love", "coding"};
    int k = 2;
    vector<string> result = topKFrequent(words, k);
    for (string word : result) {
        cout << word << " ";
    }
    // 输出 "i love"

    return 0;
}

这里定义了一个结构体`WordFreq`，用于存储单词和出现次数。在结构体中，重载了小于运算符，使得在堆中按照出现次数和字母顺序来排序。

在`topKFrequent`函数中，遍历单词列表，统计每个单词出现次数，然后将它们插入到大小为k的小根堆中。在插入时，如果堆的大小超过了k，就将堆中的最小元素弹出。

最后，将堆中的元素按照出现次数和字母顺序从大到小排序，将它们存储到一个vector中，返回即可。