面试经典150题 P380 O(1) 时间插入、删除和获取随机元素

---

时间轴

时间轴

2025-10-04

init

哈希表，vector O(1)删除

---

题目：

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

https://leetcode.cn/problems/insert-delete-getrandom-o1/description/?envType=study-plan-v2&envId=top-interview-150

这题我本来以为 getRandom 只要概率相同即可，但是这个题检测时大概率设置了随机数种子，如果不是调用 rand()得出来的顺序必定和答案不同。这题主要用 hashmap 存储 val,index，用 vector 做随机访问插入时直接放入 vector 的最后一位，删除时将被删除的元素与最后一个元素交换位置，然后弹出最后一个元素 pop_back(),要记得更改 hashmap 中因为交换而使得最后一个元素的 Index。

#include <algorithm>
#include <unordered_map>
#include <vector>

using std::unordered_map;
using std::vector;

class RandomizedSet {
    private:
        unordered_map<int, int> umap;
        vector<int> vec;

    public:
        RandomizedSet()
        {
        }

        bool insert(int val)
        {
                if (umap.count(val) == 0) {
                        vec.push_back(val);
                        umap[val] = vec.size() - 1;
                        return true;
                } else {
                        return false;
                }
        }

        bool remove(int val)
        {
                if (umap.count(val) == 0) {
                        return false;
                } else {
                        umap[vec.back()] = umap[val];
                        std::swap(vec[umap[val]], vec.back());

                        vec.pop_back();
                        umap.erase(val);

                        return true;
                }
        }

        int getRandom()
        {
                return vec[std::rand() % vec.size()];
        }
};