题目重点：访问流持续回调后返回当前第一个未重复 user ID，追问第 N 个。解释频次加有序唯一集合、不再恢复的二次访问及 O(1)/O(N) 与有序统计树取舍。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- ‘没有重复访问过’指到当前时刻累计恰好出现一次；访问顺序为流到达顺序，返回最早的仍只出现一次的 ID。第 N 个采用从 1 开始计数。
- 同一 ID 第三次及以后仍是重复，不因新一次访问重新成为候选。无候选或 N 超过候选数返回 None；N≤0 报输入错误。
- 代码以单线程顺序回调为训练接口；若并发调用，必须对计数和有序集合共同加锁或串行化，不能只保护其中一份状态。
解题路线
- 维护 count[user]，以及只存当前 count=1 用户的有序集合。首次访问追加到尾部；第二次访问从集合删除；后续访问仅增加计数。
- 不变量：有序集合中的 ID 恰好是已读前缀内出现一次的 ID，且顺序等于首次访问顺序。因此集合头就是 first，按序数第 N 项就是 nth。
- Python OrderedDict 承担哈希索引和双向链表两种职责，首次追加与按 ID 删除平均 O(1)，first 平均 O(1)。逐项扫描 nth 是 O(N)，其中 N 为当前只出现一次的用户数。
- 若需求是高频任意 N 查询，可换支持子树有效节点数的平衡搜索树，按首次到达序号排序，更新与第 N 项查询均 O(log U)；普通链表无法随机定位第 N 项。
手动走一遍
访问 A、B、A、C 后，频次 A=2、B=1、C=1，有序候选 [B,C]；first=B，nth(2)=C。再访问 B，候选只剩 [C]；再次访问 A 不会把 A 放回。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Track currently unique visitors in their first-visit order."""
from collections import OrderedDict
class UniqueVisitors:
def __init__(self) -> None:
self.count: dict[str, int] = {}
self.unique: OrderedDict[str, None] = OrderedDict()
def visit(self, user_id: str) -> None:
previous = self.count.get(user_id, 0)
self.count[user_id] = previous + 1
if previous == 0:
self.unique[user_id] = None
elif previous == 1:
del self.unique[user_id]
def first(self) -> str | None:
return next(iter(self.unique), None)
def nth(self, n: int) -> str | None:
if n < 1:
raise ValueError("n is one-based and must be positive")
for position, user_id in enumerate(self.unique, start=1):
if position == n:
return user_id
return None
复杂度
U 为历史不同用户数，N 为当前唯一用户数：每次 visit 和 first 平均 O(1)，nth O(N)，count+有序集合占 O(U)。若要求保存全流做审计，还需 O(总访问数) 事件存储；本题在线答案不需要。
易错点与追问
容易失分的边界
- 只用普通队列，在第二次访问时无法 O(1) 从中间移除；可惰性跳过队首，但第 N 个查询仍需额外策略。
- 把‘未重复’理解为从未见过的用户，结果会在首次访问后立即消失，与题目所指只出现一次不同。
- 第三次访问时错误地重新插入集合，忘记候选资格只能从 0→1 获得、1→2 失去。
- 声称链表能 O(1) 找第 N 个；如果没有序数索引，必须走过前 N−1 项。
继续深挖
- 若支持删除一次访问，count=2→1 时需要恢复原首访位置；现有候选集合已删掉该节点，需保留完整历史顺序索引。
- 若定义改为最近 24 小时恰好访问一次，过期事件会使频次回退，如何维护时间队列与候选顺序？
- 如果更新与查询分散在多实例，怎样定义全局到达顺序、序列化写入并提供一致读？
