流式日志 Top-K 高频统计

2026/05/28 09:49:28

编程算法·9 min read

滑动窗口有序集合 Top-K 哈希表华为笔试

Part 0

题目描述

在大数据实时监控系统中，服务器每秒产生海量日志数据。需要实现一个滑动窗口内的流式 Top-K 高频词统计组件，支持两种操作：

操作定义

add(word)：向大小为 $$W$$ 的滑动窗口添加关键词。

窗口满时按 FIFO 淘汰最早元素
被淘汰词的频率减 1，频率归零则从统计中移除

get_top(k)：返回窗口内频率最高的 $$k$$ 个词。

按频率降序排列；频率相同按字典序升序
有效词不足 $$k$$ 个时返回所有有效词

输入 / 输出格式

输入：第一行 $$W$$ （窗口大小）和 $$Q$$ （操作数），范围 $$[1, 10^5]$$ 。接下来 $$Q$$ 行，每行 add x 或 get k。

输出：对每个 get k 操作输出一行结果，词间空格分隔。

约束：窗口非空时才会有 get 操作；每个用例至少一次 get；内存限制 256 MB，时间 2 s。

Part 1

样例分析

样例 1

输入：

5 10
add banana
add apple
add cherry
add banana
add apple
get 3
add durian
add apple
add pipeapple
get 5

输出：

apple banana cherry
apple banana durian pipeapple

解释：

操作 1-5：队列 [banana, apple, cherry, banana, apple]，频率 banana:2, apple:2, cherry:1
操作 6：频率相同，字典序 apple < banana，输出 apple banana cherry
操作 7-9：窗口滑动淘汰 banana, cherry, banana。最终频率 apple:2, banana:1, durian:1, pipeapple:1
操作 10：k=5 但只有 4 个词，按规则输出 apple banana durian pipeapple

样例 2（窗口全替换）

输入：

3 8
add a
add b
add a
get 2
add b
add b
add b
get 2

输出：

a b
b

解释：操作 5-7 连续 add b，窗口从 [a, b, a] 完全替换为 [b, b, b]，a 被淘汰干净。最终只有 b:3 一个词。

Part 2

核心思路

这道题的核心挑战在于：窗口滑动时需要频繁地增删频率并实时维护排序。朴素做法每次 get 时重新排序，时间 $O(N \log N)$ ，面对 $$Q = 10^5$$ 必然 TLE（统计显示 11/24 TLE）。

关键观察

观察 1：窗口是 FIFO 队列，add 操作只需知道队首元素即可决定淘汰谁。

观察 2：频率变化只发生在「+1（新词入队）」和「-1（旧词出队）」两种操作上，每次只影响一个词的频率。

观察 3：如果维护一个按 (频率, 词典序) 排序的有序集合，每次频率变化时先删旧条目再插新条目，就能在 $O(\log n)$ 内完成维护。

数据结构选择：

哈希表 freq：word → 当前频率， $$O(1)$$ 查询与更新
有序集合 sorted_set：存储 (−freq, word) 元组，利用有序集合自动排序
双端队列 queue：维护 FIFO 窗口

操作	步骤	复杂度
add(word)	若窗口满，pop 队首，旧词频率 -1（从有序集合删旧条目、插新条目或删除）新词 push 入队尾，频率 +1（同理更新有序集合）	$O(\log N)$
get(k)	遍历有序集合前 $$k$$ 个元素	$$O(k)$$

为什么用 (-freq, word) 而非 (freq, word)

因为我们需要频率降序、字典序升序的双重排序。用负频率后，有序集合的自然排序恰好满足： $$(-3, "a") < (-2, "b") < (-2, "c")$$ ，即频率高的在前，同频率按字典序。

Part 3

代码实现

Python 实现使用 SortedList（来自 sortedcontainers 库），C++ 使用 std::set。两者都提供 $O(\log n)$ 的插入、删除和有序遍历。

import sys
from collections import deque
from sortedcontainers import SortedList

def solve():
    input_data = sys.stdin.buffer.read().decode().splitlines()
    idx = 0
    W, Q = map(int, input_data[idx].split())
    idx += 1

    freq = {}           # word -> count
    sl = SortedList()   # 存储 (-freq, word)，自动按频率降序 + 字典序升序
    queue = deque()      # FIFO 窗口
    output = []

    for _ in range(Q):
        parts = input_data[idx].split()
        idx += 1

        if parts[0] == 'add':
            word = parts[1]

            # 窗口满则淘汰队首
            if len(queue) == W:
                old = queue.popleft()
                # 从有序集合中删除旧条目
                sl.discard((-freq[old], old))
                freq[old] -= 1
                if freq[old] > 0:
                    sl.add((-freq[old], old))
                else:
                    del freq[old]

            # 添加新词
            if word in freq and freq[word] > 0:
                sl.discard((-freq[word], word))
            freq[word] = freq.get(word, 0) + 1
            sl.add((-freq[word], word))
            queue.append(word)

        else:  # get
            k = int(parts[1])
            result = []
            for i in range(min(k, len(sl))):
                result.append(sl[i][1])
            output.append(' '.join(result))

    sys.stdout.write('\n'.join(output) + '\n')

solve()

#include <bits/stdc++.h>
using namespace std;

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

    int W, Q;
    cin >> W >> Q;

    unordered_map<string, int> freq;
    // set 默认升序，存储 (-freq, word)
    set<pair<int, string>> sl;
    deque<string> que;

    while (Q--) {
        string op;
        cin >> op;

        if (op == "add") {
            string word;
            cin >> word;

            // 窗口满则淘汰队首
            if ((int)que.size() == W) {
                string old = que.front();
                que.pop_front();
                sl.erase({-freq[old], old});
                freq[old]--;
                if (freq[old] > 0) {
                    sl.insert({-freq[old], old});
                } else {
                    freq.erase(old);
                }
            }

            // 添加新词
            if (freq.count(word) && freq[word] > 0) {
                sl.erase({-freq[word], word});
            }
            freq[word]++;
            sl.insert({-freq[word], word});
            que.push_back(word);

        } else { // get
            int k;
            cin >> k;

            bool first = true;
            int cnt = 0;
            for (auto it = sl.begin(); it != sl.end() && cnt < k; ++it, ++cnt) {
                if (!first) cout << ' ';
                cout << it->second;
                first = false;
            }
            cout << '\n';
        }
    }
    return 0;
}

关键细节：SortedList.discard 安全删除（不存在时不报错），而 std::set.erase 同样安全。窗口淘汰时必须先删旧条目再更新频率再插回（或删除），顺序不能乱。

Part 4

复杂度分析

维度	复杂度	说明
时间	$O(Q \log N)$	每次 add 最多 2 次有序集合插入/删除， $O(\log N)$ ；每次 get 遍历前 $$k$$ 项， $$O(k)$$ ，总 $$Q$$ 次操作
空间	$$O(W)$$	窗口最多存 $$W$$ 个词，哈希表和有序集合规模不超过 $$W$$

对比朴素做法：每次 get 排序 $O(N \log N)$ ，总复杂度 $O(Q \cdot N \log N)$ ， $$N$$ 最大 $$10^5$$ ，显然 TLE。而有序集合方案将单次维护降至 $O(\log N)$ ，总量 $O(Q \log N) \approx 10^5 \times 17 \approx 1.7 \times 10^6$ ，稳过。

参考来源

题目原址 — CodeFun2000 P4983