词频统计

形式化题目

有 $n$ 篇文章，每篇文章是一个整数序列，其中每个整数（单词编号）都在 $1 \sim m$ 内。

对每个单词 $i \in [1, m]$ ，统计两个量并输出：

单词 $i$ 出现在了多少篇文章中（同一篇文章内多次出现只算一篇）；
单词 $i$ 在所有文章中出现的总次数。

思路

这是两个不同的统计量，需要分别维护：总次数每次读到单词就累加；文章数只在单词于当前文章中第一次出现时累加。

朴素做法：每篇文章用集合去重

先看一个容易理解的想法：每篇文章用一个集合记录本次出现过的单词，文章读完后把集合里的单词文章数各加一。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，用集合记录单篇文章出现过的单词，避免同一篇文章重复统计。
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 100005;

int n, m;
int article_count[MAXM]; // article_count[word] 表示单词 word 出现在多少篇文章中
int total_count[MAXM];   // total_count[word] 表示单词 word 在所有文章中出现的总次数

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int article = 1; article <= n; article++) {
        int length;
        cin >> length;
        set<int> appeared; // 当前这篇文章出现过的单词，set 保证同一单词只记录一次
        for (int j = 0; j < length; j++) {
            int word;
            cin >> word;
            total_count[word]++;
            appeared.insert(word);
        }
        // 文章读完后再把每个出现过的单词文章数加一
        for (set<int>::iterator it = appeared.begin(); it != appeared.end(); ++it) {
            article_count[*it]++;
        }
    }

    for (int word = 1; word <= m; word++) {
        cout << article_count[word] << ' ' << total_count[word] << '\n';
    }

    return 0;
}

这个做法正确，但每篇文章都要维护一个集合，多了一层 $\log$ 的代价。

优化：用文章编号代替集合去重

既然文章是按 $1 \sim n$ 顺序扫描的，可以用一个数组 last_article[word] 记录单词 word 最近一次累加文章数时的文章编号：

读到单词 word，先把 total_count[word] 加一；
若 last_article[word] != 当前文章编号，说明这是当前文章中第一次出现，last_article[word] 更新为当前编号，并把 article_count[word] 加一。

这样不需要任何集合结构，也不需要为每篇文章清空数组，扫描一遍即可完成两个统计量。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 100005;

int n, m;
int article_count[MAXM]; // article_count[word] 表示单词 word 出现在多少篇文章中
int total_count[MAXM];   // total_count[word] 表示单词 word 在所有文章中出现的总次数
int last_article[MAXM];  // last_article[word] 表示单词 word 最近一次统计文章数的文章编号

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int article = 1; article <= n; article++) {
        int length;
        cin >> length;
        for (int j = 0; j < length; j++) {
            int word;
            cin >> word;
            total_count[word]++;
            // 同一个单词在同一篇文章中只统计一次文章数
            if (last_article[word] != article) {
                last_article[word] = article;
                article_count[word]++;
            }
        }
    }

    for (int word = 1; word <= m; word++) {
        cout << article_count[word] << ' ' << total_count[word] << '\n';
    }

    return 0;
}

复杂度

设所有文章中的单词总数为 $S$ （ $S = \sum l_i$ ）。

时间：每读到一个单词做 $O(1)$ 的累加与判断，总时间复杂度 $O(S)$ ；朴素集合做法为 $O(S \log S)$ 。
空间：三个大小为 $m + 1$ 的数组，空间复杂度 $O(m)$ 。

总结

“出现总次数”与“出现文章数”是两个不同的统计量：前者每次出现都累加，后者同一篇文章内只能累加一次。用文章编号记录上次统计位置，就能在不引入集合的情况下完成去重，这是常见的“按顺序扫描 + 编号标记”技巧。

目录

形式化题目

思路

朴素做法：每篇文章用集合去重

优化：用文章编号代替集合去重

代码

复杂度

总结