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

这道题到底在问什么

操作

insert(1),insert(2),remove(1)

再

getRandom()

返回

只可能是 2

最优解：一步一步想明白

1. 3两种结构各有一个 O(1) 死穴。聪明做法是两个一起用,让它们互相补上对方的短板。
2. 4下面用 vals 数组(格子)配 idx 哈希表,把 insert / remove / getRandom 一步步演给你看。盯住格子的增减和哈希项的同步。
3. 5vals = [] ,idx = {}全空开局。每次 insert 都做两件事:值追加到数组尾 + 在 idx 记下它的新下标。
4. 6vals=[1] ,idx{1:0}插入 1:数组多出一格放在尾部(下标 0),同时 idx 里新增一项 1→0。追加 + 记下标,都是 O(1)。
5. 7vals=[1,2] ,idx{1:0,2:1}插入 2:再在尾部多一格(下标 1),idx 新增 2→1。数组真的长出来一格了。
6. 8vals=[1,2,3] ,idx{1:0,2:1,3:2}插入 3:尾部再添一格(下标 2),idx 新增 3→2。现在 vals=[1,2,3],idx 三项齐全。
7. 9查 idx → 2 在下标 1删除 2:先用 idx 一秒查到它在下标 1。麻烦在于它不在末尾——直接删会留空洞、要搬后面的。下一帧看妙招。
8. 10末尾 3 填进下标 1妙招:把最后一个元素 3 搬过来盖在 2 的位置(下标 1)。3 换了座位,所以 idx 里 3 的下标也改成 1。末尾那格(灰)即将被丢掉。
9. 11vals=[1,3] ,idx{1:0,3:1}弹出末尾那格(数组缩回 2 格),再把 idx 里 2 这项删掉。因为只动了末尾,删除中间元素也只花 O(1)!现在 vals=[1,3]。
10. 12vals=[1,3,4] ,idx{1:0,3:1,4:2}再插入 4:照旧追加到尾(下标 2),idx 新增 4→2。数组又长回 3 格,vals=[1,3,4]。
11. 13随机下标 ∈ {0,1,2}随机取数:只要在 0~2 里摇一个下标,直接读数组那一格。这次摇到 1,返回 3。数组紧凑无空洞,每格等概率——这就是为什么必须用数组兜底。
12. 14这次摇到下标 0getRandom 不改任何数据,纯读。再摇一次可能摇到 0,返回 1。每个下标被摇中的概率都是 1/3——这就是「等概率」。
13. 15没有空洞 → 等概率成立删除用「换尾 + 弹出」而不是留空洞,正是为了让数组始终紧凑;紧凑数组的 random 下标才是真等概率。idx 表则保证删除前能 O(1) 找到位置。
14. 16上一串删的是中间(2)。这次专挑删开头(1)——看末尾的元素如何一路换到下标 0,以及它的 idx 怎么同步。当前 vals=[1,3,4]。
15. 17vals=[1,3,4,5] ,idx+{5:3}先插入 5:尾部多一格(下标 3),idx 新增 5→3。数组长到 4 格 [1,3,4,5]。
16. 18查 idx → 1 在下标 0删除 1:idx 一秒告诉我们它在下标 0(最前面)。要是直接删,后面 3 个全得前移——O(n)。还是用换尾大法。
17. 19末尾 5 填进下标 0把最后一个元素 5 搬到开头(下标 0)盖掉 1。5 换了座位,所以 idx[5] 改成 0。末尾那格(灰)待丢。
18. 20vals=[5,3,4] ,idx{3:1,4:2,5:0}弹掉末尾(数组缩回 3 格),再从 idx 删掉 1 这项。哪怕删的是开头,也只动了两个位置——依旧 O(1)。现在 vals=[5,3,4]。
19. 21随机下标 ∈ {0,1,2}数组还是紧凑的 [5,3,4],随机摇 0~2 的下标。这次摇到 2,返回 4。三格依旧等概率,删头丝毫没破坏这一点。
20. 22vals=[5,3,4,1] ,idx+{1:3}把删过的 1 再加回来:idx 里查无 1,允许插入。它追加到新尾部(下标 3),idx 新增 1→3——注意它的下标变成 3 了,跟最初的 0 没关系。
21. 23idx 里已有 1 → 返回 false要是再插一次 1:idx 一查发现已经有了,直接返回 false,数组和表原封不动。这就是 O(1) 查重——边界一里的情况。
22. 24vals 紧凑 + idx 下标精确看这一路:每次操作后,数组都是紧凑的、idx 里每项下标都精确指向数组位置。这份「时刻对齐」就是三个操作都能 O(1) 的根。
23. 28idx[3] 还停在旧下标 2 → 错假如换尾后忘记 idx[last] = i:3 明明在下标 1,表里却还记成 2。下次 remove(3) 会去摸下标 2——越界或删错元素。这就是雷区②的后果。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

import random
class RandomizedSet:
    def __init__(self):
        self.vals = []           # 数组: 供随机
        self.idx = {}            # 值 -> 下标
    def insert(self, val):
        if val in self.idx: return False
        self.idx[val] = len(self.vals)
        self.vals.append(val)
        return True
    def remove(self, val):
        if val not in self.idx: return False
        i = self.idx[val]; last = self.vals[-1]
        self.vals[i] = last; self.idx[last] = i
        self.vals.pop(); del self.idx[val]
        return True
    def getRandom(self):
        return random.choice(self.vals)

class RandomizedSet {
    vector<int> vals;
    unordered_map<int,int> idx;   // 值 -> 下标
public:
    bool insert(int val) {
        if (idx.count(val)) return false;
        idx[val] = vals.size();
        vals.push_back(val);
        return true;
    }
    bool remove(int val) {
        if (!idx.count(val)) return false;
        int i = idx[val], last = vals.back();
        vals[i] = last; idx[last] = i;
        vals.pop_back(); idx.erase(val);
        return true;
    }
    int getRandom() { return vals[rand() % vals.size()]; }
};

class RandomizedSet {
    private List<Integer> vals = new ArrayList<>();
    private Map<Integer,Integer> idx = new HashMap<>();
    private Random rand = new Random();
    public boolean insert(int val) {
        if (idx.containsKey(val)) return false;
        idx.put(val, vals.size());
        vals.add(val);
        return true;
    }
    public boolean remove(int val) {
        if (!idx.containsKey(val)) return false;
        int i = idx.get(val);
        int last = vals.get(vals.size() - 1);
        vals.set(i, last); idx.put(last, i);
        vals.remove(vals.size() - 1); idx.remove(val);
        return true;
    }
    public int getRandom() {
        return vals.get(rand.nextInt(vals.size()));
    }
}

复杂度

面试官可能追问