HJ144. 小红书推荐系统
题目描述
给定小红的搜索记录（分词后的结果），单词出现次数不少于 3 次的即为"关键词"。请按搜索频次从高到低输出所有关键词；频次相同则按字典序升序输出。
输入格式
一行字符串，仅由小写字母和空格组成。
输出格式
每行一个关键词，按频次降序、同频字典序升序输出。
示例
示例 1
输入：
kou red game red ok who game red karaoke yukari kou red red nani kou can koukou ongakugame game
输出：
red
game
kou
说明：
red 出现 4 次，game、kou 各出现 3 次，为关键词；按频次降序、同频字典序升序输出。
解题思路
第一步：理解问题本质
把字符串按空格分词，统计每个单词出现次数，过滤出出现不少于 3 次的，再按"频次降序、同频字典序升序"排序输出。
第二步：暴力解法（手写计数 + 排序）
用一个字典手动统计次数，再对字典项按规则排序。可工作但代码略长。
第三步：优化解法（Counter + 排序）
Python 的 collections.Counter 一次性完成计数：
cnt = Counter(s.split())
keywords = [(w, c) for w, c in cnt.items() if c >= 3]
keywords.sort(key=lambda x: (-x[1], x[0]))
排序键用 (-频次, 单词)，-频次 实现降序，单词默认升序即字典序。
第四步：最终实现
过滤出次数 >= 3 的单词，按上述排序键排序，逐行输出。
完整代码实现
算法可视化 · 逐帧回放这道题的代码13 帧 · 录制输入
import sys
from collections import Counter
def solve() -> None:
s = sys.stdin.readline().strip()
words = s.split()
cnt = Counter(words)
# 过滤出现 >= 3 次的单词
keywords = [(w, c) for w, c in cnt.items() if c >= 3]
# 频次降序，同频字典序升序
keywords.sort(key=lambda x: (-x[1], x[0]))
for w, _ in keywords:
print(w)
if __name__ == "__main__":
solve()
示例推演
以示例 1 为例，分词后统计：
red: 4 次game: 3 次kou: 3 次- 其余单词（
ok、who、karaoke、yukari、nani、can、koukou、ongakugame）均 < 3 次，被过滤。
过滤后的候选：[(red,4), (game,3), (kou,3)]。
按 (-频次, 单词) 排序：
red频次 4 排最前game、kou频次同为 3，按字典序game<kou，所以game在前
输出顺序：red、game、kou，正确。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 手写计数+排序 | O(N + U·log U) | O(U) | U 为不同单词数 |
| Counter+排序 | O(N + U·log U) | O(U) | 简洁高效 |
N 为总单词数，U 为去重后的不同单词数
易错点总结
1. 排序键写反
要求"频次降序、同频字典序升序"，键应为 (-x[1], x[0])。若写成 (x[0], -x[1]) 会变成先按字典序排，错误。
2. 过滤条件写错
关键词是"出现不少于 3 次"，条件是 c >= 3，写成 c > 3 会漏掉恰好 3 次的单词。
3. 输出格式
每行一个单词，直接用 print(w) 即可，不需要拼接。
扩展思考
- 这是经典的"词频统计 + 多关键字排序"问题，可扩展到 Top-K 热门词、TF-IDF 等文本挖掘场景。
- 若数据量巨大，可用堆维护 Top-K 而非全量排序，将复杂度降为 O(N + U·log K)。