小红书推荐系统

[题目链接](https://www.nowcoder.com/practice/e5b39c9034a84bf2a5e026b2b9b973d0)

思路

本题是一道哈希表 + 排序的基础题。

统计词频

将输入字符串按空格分词后，用哈希表统计每个单词的出现次数。

筛选关键词

遍历哈希表，保留出现次数 $\geq 3$ 的单词。

自定义排序

对筛选出的关键词按以下规则排序：

频次降序：出现次数多的排前面；
字典序升序：频次相同时，按字母顺序排列。

样例演示

输入 kou red game red ok who game red karaoke yukari kou red red nani kou can koukou ongakugame game，统计词频后：

单词	次数
red	5
game	3
kou	3
ok, who, karaoke, ...	1

次数 $\geq 3$ 的有 red(5)、game(3)、kou(3)。按频次降序、字典序升序排列后输出 red、game、kou。

复杂度

时间复杂度： $O(n + m \log m)$ ，其中 $n$ 为字符串长度， $m$ 为不同单词数。分词和统计为 $O(n)$ ，排序为 $O(m \log m)$ 。
空间复杂度： $O(n)$ ，哈希表存储所有单词。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    string line;
    getline(cin, line);
    istringstream iss(line);
    string w;
    map<string,int> cnt;
    while(iss >> w) cnt[w]++;
    vector<pair<string,int>> v;
    for(auto &p : cnt) if(p.second >= 3) v.push_back(p);
    sort(v.begin(), v.end(), [](auto &a, auto &b){
        if(a.second != b.second) return a.second > b.second;
        return a.first < b.first;
    });
    for(auto &p : v) cout << p.first << "\n";
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] words = line.split(" ");
        Map<String, Integer> cnt = new HashMap<>();
        for (String w : words) {
            if (w.isEmpty()) continue;
            cnt.put(w, cnt.getOrDefault(w, 0) + 1);
        }
        List<Map.Entry<String, Integer>> list = new ArrayList<>();
        for (Map.Entry<String, Integer> e : cnt.entrySet()) {
            if (e.getValue() >= 3) list.add(e);
        }
        list.sort((a, b) -> {
            if (!a.getValue().equals(b.getValue())) return b.getValue() - a.getValue();
            return a.getKey().compareTo(b.getKey());
        });
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<String, Integer> e : list) {
            sb.append(e.getKey()).append("\n");
        }
        System.out.print(sb);
    }
}

from collections import Counter

line = input()
cnt = Counter(line.split())
keywords = [(w, c) for w, c in cnt.items() if c >= 3]
keywords.sort(key=lambda x: (-x[1], x[0]))
print('\n'.join(w for w, c in keywords))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const words = line.split(' ').filter(w => w.length > 0);
    const cnt = {};
    for (const w of words) cnt[w] = (cnt[w] || 0) + 1;
    const keywords = Object.entries(cnt).filter(([w, c]) => c >= 3);
    keywords.sort((a, b) => {
        if (a[1] !== b[1]) return b[1] - a[1];
        return a[0] < b[0] ? -1 : 1;
    });
    console.log(keywords.map(([w]) => w).join('\n'));
    rl.close();
});