小红书推荐算法

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

思路

本题的核心是：给定若干商品及其关键词属性，以及用户搜索过的关键词，按每个商品匹配到的用户关键词数量降序排列，匹配数相同则保持原始输入顺序。

做法

读入用户关键词，存入哈希集合，以便 $O(1)$ 查询某个属性是否为用户搜索过的关键词。
遍历每个商品，统计它的属性中有多少个出现在用户关键词集合里，记为该商品的匹配数。
稳定排序：按匹配数从大到小做一次稳定排序（stable sort），匹配数相同的商品自然保持输入顺序。
输出排序后的商品名称。

样例演示

用户关键词：{red, book, game, music, sigma}。

mozart 的属性 {book, classic, music} 中匹配了 book, music，匹配数为 2。
arcaea 的属性 {red, music, game, hard} 中匹配了 red, music, game，匹配数为 3。

按匹配数降序：arcaea(3), mozart(2)。

复杂度分析

时间复杂度： $O(S + n \log n)$ ，其中 $S$ 是所有商品属性数量之和， $n$ 是商品数量。哈希查询每次 $O(1)$ ，排序 $O(n \log n)$ 。
空间复杂度： $O(S + m)$ ，其中 $m$ 是用户关键词数量。

代码

C++
Java

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    set<string> keywords;
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        keywords.insert(s);
    }

    vector<pair<string, int>> products;
    for (int i = 0; i < n; i++) {
        string name;
        int k;
        cin >> name >> k;
        int cnt = 0;
        for (int j = 0; j < k; j++) {
            string attr;
            cin >> attr;
            if (keywords.count(attr)) cnt++;
        }
        products.push_back({name, cnt});
    }

    stable_sort(products.begin(), products.end(), [](const pair<string,int>& a, const pair<string,int>& b) {
        return a.second > b.second;
    });

    for (auto& p : products) {
        cout << p.first << "\n";
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();

        Set<String> keywords = new HashSet<>();
        for (int i = 0; i < m; i++) {
            keywords.add(sc.next());
        }

        String[] names = new String[n];
        int[] counts = new int[n];
        for (int i = 0; i < n; i++) {
            names[i] = sc.next();
            int k = sc.nextInt();
            int cnt = 0;
            for (int j = 0; j < k; j++) {
                if (keywords.contains(sc.next())) cnt++;
            }
            counts[i] = cnt;
        }

        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> {
            if (counts[a] != counts[b]) return counts[b] - counts[a];
            return a - b;
        });

        StringBuilder sb = new StringBuilder();
        for (int i : idx) {
            sb.append(names[i]).append('\n');
        }
        System.out.print(sb);
    }
}