题目重点：按题目两次澄清后的最终题意，以哈希表和双向链表实现 log 与 firstUser 均最坏 O(1)。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 一次登录就是同一 userId 的一次出现；第二次出现后该 userId 永远不再合格，后续登录不能让它重新变成唯一。
- 无符合用户时返回 None；不支持撤销登录，哈希表按通常模型视为期望 O(1) 查找，若严格要求对抗性哈希碰撞下的绝对最坏 O(1)，需另讨论字典模型。
解题路线
- 双向链表按首次登录顺序只保存恰好出现一次的用户，链表头始终是答案；哈希表记录用户未出现、当前节点或已重复状态。
- 首次登录创建节点并追加尾部。第二次登录通过表找到节点，直接 O(1) 把它从链表摘下，并把表值设为已重复。之后再登录不改变状态。
- firstUser 直接看哨兵 head 的下一节点。归纳不变量：链表恰含所有出现次数为一的用户，顺序为首次出现时间顺序。
- 队列惰性删除虽均摊可达 O(1)，某次 firstUser 可能一次弹出大量失效用户，违背题目特别要求的单次最坏界。
手动走一遍
依次 log(A)、log(B)、log(A)：链表由 [A] 到 [A,B] 再到 [B]，firstUser 返回 B；再 log(B) 后链表空，返回 None。随后再 log(A)，A 已重复，不能重新入链。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""O(1) worst-case update and query for earliest user seen exactly once."""
class Node:
__slots__ = ("user", "prev", "next")
def __init__(self, user: str | None = None):
self.user = user
self.prev: Node | None = None
self.next: Node | None = None
class FirstUniqueLogin:
def __init__(self):
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
self.state: dict[str, Node | None] = {}
def log(self, user: str) -> None:
if user not in self.state:
node = Node(user)
last = self.tail.prev
assert last is not None
last.next = node
node.prev = last
node.next = self.tail
self.tail.prev = node
self.state[user] = node
elif (node := self.state[user]) is not None:
previous, following = node.prev, node.next
assert previous is not None and following is not None
previous.next = following
following.prev = previous
self.state[user] = None
def first_user(self) -> str | None:
first = self.head.next
assert first is not None
return None if first is self.tail else first.user
复杂度
在通常哈希表期望 O(1) 模型下，log 与 firstUser 均 O(1) 时间，空间 O(U)，U 为不同 userId 数。链表移除与读取头节点本身为确定性 O(1)；若将哈希碰撞纳入最坏界，需说明输入域与字典实现。
易错点与追问
容易失分的边界
- 用两个 set 只能知道谁出现一次，无法 O(1) 找最早者。
- 用 queue+延迟删除，只证明均摊 O(1) 却声称每次最坏 O(1)。
- 第二次登录移除节点后，把用户从表中完全删除，第三次又被当首次登录。
继续深挖
- 若操作增加撤销最近一次登录，状态和时间顺序应怎样变化？
- 如果 userId 范围已知且有限，可否用直接寻址表给出真正最坏 O(1)？空间代价是什么？
