O(1) 时间插入、删除和获取随机元素

两种结构各有一个 O(1) 死穴。聪明做法是两个一起用,让它们互相补上对方的短板。

下面用 vals 数组(格子)配 idx 哈希表,把 insert / remove / getRandom 一步步演给你看。盯住格子的增减和哈希项的同步。

起步 · 空集合：全空开局。每次 insert 都做两件事:值追加到数组尾 + 在 idx 记下它的新下标。

insert(1) · 追加到尾：插入 1:数组多出一格放在尾部(下标 0),同时 idx 里新增一项 1→0。追加 + 记下标,都是 O(1)。

insert(2) · 追加到尾：插入 2:再在尾部多一格(下标 1),idx 新增 2→1。数组真的长出来一格了。

insert(3) · 追加到尾：插入 3:尾部再添一格(下标 2),idx 新增 3→2。现在 vals=[1,2,3],idx 三项齐全。

remove(2) · 先定位：删除 2:先用 idx 一秒查到它在下标 1。麻烦在于它不在末尾——直接删会留空洞、要搬后面的。下一帧看妙招。

remove(2) · 与尾元素交换：妙招:把最后一个元素 3 搬过来盖在 2 的位置(下标 1)。3 换了座位,所以 idx 里 3 的下标也改成 1。末尾那格(灰)即将被丢掉。

remove(2) · 弹出尾 + 删表项：弹出末尾那格(数组缩回 2 格),再把 idx 里 2 这项删掉。因为只动了末尾,删除中间元素也只花 O(1)!现在 vals=[1,3]。

insert(4) · 追加到尾：再插入 4:照旧追加到尾(下标 2),idx 新增 4→2。数组又长回 3 格,vals=[1,3,4]。

getRandom() · 摇下标：随机取数:只要在 0~2 里摇一个下标,直接读数组那一格。这次摇到 1,返回 3。数组紧凑无空洞,每格等概率——这就是为什么必须用数组兜底。

getRandom() · 换个种子再摇：getRandom 不改任何数据,纯读。再摇一次可能摇到 0,返回 1。每个下标被摇中的概率都是 1/3——这就是「等概率」。

回看 · 数组为何必须紧凑：删除用「换尾 + 弹出」而不是留空洞,正是为了让数组始终紧凑;紧凑数组的 random 下标才是真等概率。idx 表则保证删除前能 O(1) 找到位置。

上一串删的是中间(2)。这次专挑删开头(1)——看末尾的元素如何一路换到下标 0,以及它的 idx 怎么同步。当前 vals=[1,3,4]。

insert(5) · 追加到尾：先插入 5:尾部多一格(下标 3),idx 新增 5→3。数组长到 4 格 [1,3,4,5]。

remove(1) · 先定位：删除 1:idx 一秒告诉我们它在下标 0(最前面)。要是直接删,后面 3 个全得前移——O(n)。还是用换尾大法。

remove(1) · 与尾元素 5 交换：把最后一个元素 5 搬到开头(下标 0)盖掉 1。5 换了座位,所以 idx[5] 改成 0。末尾那格(灰)待丢。

remove(1) · 弹出尾 + 删表项：弹掉末尾(数组缩回 3 格),再从 idx 删掉 1 这项。哪怕删的是开头,也只动了两个位置——依旧 O(1)。现在 vals=[5,3,4]。

getRandom() · 再摇一次：数组还是紧凑的 [5,3,4],随机摇 0~2 的下标。这次摇到 2,返回 4。三格依旧等概率,删头丝毫没破坏这一点。

insert(1) · 删过的值再加回来：把删过的 1 再加回来:idx 里查无 1,允许插入。它追加到新尾部(下标 3),idx 新增 1→3——注意它的下标变成 3 了,跟最初的 0 没关系。

insert(1) 重复 · 被挡下：要是再插一次 1:idx 一查发现已经有了,直接返回 false,数组和表原封不动。这就是 O(1) 查重——边界一里的情况。

全程回看 · 双结构始终对齐：看这一路:每次操作后,数组都是紧凑的、idx 里每项下标都精确指向数组位置。这份「时刻对齐」就是三个操作都能 O(1) 的根。

雷区实演 · 交换后漏更新 idx：假如换尾后忘记 idx[last] = i:3 明明在下标 1,表里却还记成 2。下次 remove(3) 会去摸下标 2——越界或删错元素。这就是雷区②的后果。

边界三连：查重、删不存在、删末尾这三种边界,代码里 idx 查一下就都覆盖了。

面试追问：把「双结构分工」「换尾三连」「381 进阶」讲清,这道设计题面试就稳了。