实时社交媒体热点追踪

题意

设计一个社交媒体热词追踪系统。系统维护一个带计数器的队列和一个容量为 $k$ 的展示面板。

第一行输入整数 $k$ （面板容量），之后每行输入一批空格分隔的关键词。对于每一批：

如果关键词已在队列中，计数器 +1（位置不变）
如果是新关键词，追加到队尾，计数器初始化为 1
处理完本批后，从队头取出最多 $k$ 个关键词并输出（格式：keyword count 对，空格分隔），然后将它们从队列中移除
如果队列为空（没有可输出的），输出 null
被移除的关键词如果后续再出现，视为全新热词

注意：空行也算一批输入，此时不添加任何关键词，直接进入输出阶段。

思路

这题乍一看信息量不小，但拆解下来核心操作就两个：按序存储 + 快速查找。

先想想需要什么数据结构？

队列要保持插入顺序（FIFO），同时还要能快速判断某个关键词是否已经存在——如果存在就更新计数，不存在就追加到尾部。

普通数组或链表可以保序，但查找是 $O(n)$ 的。哈希表查找是 $O(1)$ ，但不保序。怎么兼顾？

答案是有序哈希表（或者链表 + 哈希表的组合）：

用链表维护插入顺序
用哈希表记录每个关键词在链表中的位置，实现 $O(1)$ 查找和更新

在不同语言中，这个结构有现成的实现：

C++：std::list + unordered_map（手动组合）
Java：LinkedHashMap（天然有序）
Python：OrderedDict（天然有序，popitem(last=False) 弹出队头）
JavaScript：Map（ES6 规范保证插入顺序）

每一批处理流程：

遍历本批关键词，存在则计数 +1，不存在则插入队尾
从队头弹出 $\min(k, \text{队列长度})$ 个元素，拼接输出
队列为空则输出 null

整体时间复杂度 $O(B \cdot (W + k))$ ，其中 $B$ 是批次数， $W$ 是每批关键词数。由于 $B, W, k$ 均不超过 100，完全不会有性能问题。

有一个容易踩的坑：输入中的空行也是合法的一批，需要正常执行输出逻辑（此时不添加关键词，如果队列已空就输出 null）。

代码

C++
Java
Python3
JavaScript

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

int main(){
    int k;
    string line;
    getline(cin, line);
    k = stoi(line);

    list<pair<string,int>> q;
    unordered_map<string, list<pair<string,int>>::iterator> mp;

    while(getline(cin, line)){
        istringstream iss(line);
        string word;
        while(iss >> word){
            auto it = mp.find(word);
            if(it != mp.end()){
                it->second->second++;
            } else {
                q.push_back({word, 1});
                mp[word] = prev(q.end());
            }
        }

        int cnt = min(k, (int)q.size());
        if(cnt == 0){
            printf("null\n");
        } else {
            for(int i = 0; i < cnt; i++){
                if(i) printf(" ");
                printf("%s %d", q.front().first.c_str(), q.front().second);
                mp.erase(q.front().first);
                q.pop_front();
            }
            printf("\n");
        }
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine().trim());

        LinkedHashMap<String, Integer> q = new LinkedHashMap<>();
        StringBuilder sb = new StringBuilder();
        String line;
        while ((line = br.readLine()) != null) {
            line = line.trim();
            if (!line.isEmpty()) {
                String[] words = line.split("\\s+");
                for (String w : words) {
                    if (w.isEmpty()) continue;
                    q.put(w, q.getOrDefault(w, 0) + 1);
                }
            }

            int cnt = Math.min(k, q.size());
            if (cnt == 0) {
                sb.append("null\n");
            } else {
                Iterator<Map.Entry<String, Integer>> it = q.entrySet().iterator();
                for (int i = 0; i < cnt; i++) {
                    Map.Entry<String, Integer> e = it.next();
                    if (i > 0) sb.append(' ');
                    sb.append(e.getKey()).append(' ').append(e.getValue());
                    it.remove();
                }
                sb.append('\n');
            }
        }
        System.out.print(sb);
    }
}

import sys
from collections import OrderedDict

def main():
    data = sys.stdin.read()
    if data.endswith('\n'):
        data = data[:-1]
    input_data = data.split('\n')
    idx = 0
    k = int(input_data[idx]); idx += 1

    q = OrderedDict()
    out = []

    while idx < len(input_data):
        line = input_data[idx].strip(); idx += 1
        if line:
            words = line.split()
            for w in words:
                if w in q:
                    q[w] += 1
                else:
                    q[w] = 1

        cnt = min(k, len(q))
        if cnt == 0:
            out.append("null")
        else:
            parts = []
            for _ in range(cnt):
                key, val = q.popitem(last=False)
                parts.append(f"{key} {val}")
            out.append(' '.join(parts))

    print('\n'.join(out))

main()

process.stdin.resume();
process.stdin.setEncoding('utf8');
let input = '';
process.stdin.on('data', c => input += c);
process.stdin.on('end', () => {
    if (input.endsWith('\n')) input = input.slice(0, -1);
    const lines = input.split('\n');
    let idx = 0;
    const k = parseInt(lines[idx++]);

    const q = new Map();
    const out = [];

    while (idx < lines.length) {
        const line = lines[idx++].trim();
        if (line) {
            const words = line.split(/\s+/);
            for (const w of words) {
                if (!w) continue;
                q.set(w, (q.get(w) || 0) + 1);
            }
        }

        const cnt = Math.min(k, q.size);
        if (cnt === 0) {
            out.push("null");
        } else {
            const parts = [];
            let i = 0;
            const toDelete = [];
            for (const [key, val] of q) {
                if (i >= cnt) break;
                parts.push(key + ' ' + val);
                toDelete.push(key);
                i++;
            }
            for (const key of toDelete) {
                q.delete(key);
            }
            out.push(parts.join(' '));
        }
    }

    console.log(out.join('\n'));
});