Misra-Gries (k-1) 计数器在交易流上的重元素近似

实现 solution(tickers: list[str], k: int) -> list[str]。给定按到达顺序排列的代码序列 tickers（长度 N）以及整数 k >= 2，运行 Misra-Gries (k - 1) 计数器重元素近似算法，并将得到的候选集合按字典序升序作为字符串列表返回。

算法。维护至多 k - 1 项的 (ticker -> count) 表 counts。按到达顺序对每个新代码 x：

1. 若 x 已在表中，对应计数 +1。
2. 否则若当前已跟踪键数 < k - 1，把 x 以计数 1 加入表。
3. 否则（表已满且 x 未被跟踪）：把 *所有* 被跟踪计数减 1，并删除当前为 0 的键。x *不* 加入表。

整段流处理完后返回 sorted(counts.keys())。

合约。

• k >= 2 是前置条件；k < 2 时行为未定义。
• 空输入：返回 []。
• 输出是 *候选* 集合：每个真正的重元素（流中频次严格 > N / k 的代码）保证在输出里，但输出可能包含假阳性。输出规模至多 k - 1。

例

solution(["T-1", "T-2", "T-1", "T-3", "T-1", "T-2", "T-1"], 3) 返回 ["T-1", "T-2"]。

cap = k - 1 = 2 的逐步演算：

| 步 | x | 动作 | 之后 counts | |----|-----|---------------------------------------|------------------------| | 1 | T-1 | 新键，有空位 | {T-1: 1} | | 2 | T-2 | 新键，有空位 | {T-1: 1, T-2: 1} | | 3 | T-1 | 已跟踪，递增 | {T-1: 2, T-2: 1} | | 4 | T-3 | 新键，表已满 -> 全体递减 | {T-1: 1} | | 5 | T-1 | 已跟踪，递增 | {T-1: 2} | | 6 | T-2 | 新键，有空位 | {T-1: 2, T-2: 1} | | 7 | T-1 | 已跟踪，递增 | {T-1: 3, T-2: 1} |

N = 7，N / k = 7 / 3 ≈ 2.33。唯一真正的重元素是 T-1（计数 3 > 2.33）。T-2（计数 2）是候选集合中的假阳性——合约只保证“包含”而非“精确”。

无重元素的 round-robin 流——solution(["T-1", "T-2", "T-3", "T-4", "T-1", "T-2", "T-3", "T-4"], 4)——返回 []：前 3 个之后每一个新代码都触发全体递减并清空表。

k = 2 时算法退化为 Boyer-Moore 多数元素（至多跟踪 1 个键）：solution(["T-A", "T-B", "T-A", "T-A", "T-B", "T-A"], 2) 返回 ["T-A"]。

k > N + 1 时表上限超过流长，永不触发递减，输出恰是流中出现过的所有不同代码：solution(["T-A", "T-B", "T-C"], 10) 返回 ["T-A", "T-B", "T-C"]。

函数骨架见 stubs/stub.py。

实践背景

多市场股票交易桌的实时成交流通常每秒推送数十万条 print，覆盖数千个不同代码。运营面板希望即时高亮“当前正在主导成交流的代码”——即候选重元素——但既不能为每个代码各开一个内存计数器，也不能两遍扫描。Misra-Gries 是教科书式的有界内存答案：仅用 k - 1 个计数器就能保证不漏掉任何频次严格 > N / k 的真重元素，每条 print 摊还 O(1) 工作量。溢出时的“全体递减”是“当下没人主导”这一微观结构状态的廉价探针：若候选集合返回空，说明窗口内没有任何代码越过 N / k 阈值。本题考的合约细节正是生产中的陷阱——上限是 k - 1 不是 k（off-by-one 会破坏 k = 2 的 Boyer-Moore 退化），递减作用于 *每一个* 被跟踪键而非只一个（否则陈旧的“鬼魂”不断堆积，假阳率爆炸），零计数项必须淘汰（否则表永远腾不出空位让真正新崛起的主导代码进入）。