Classic 150 Interview Questions P380 Insert Delete GetRandom O(1)

---

Timeline

Timeline

2025-10-04

init

Hash table, vector O(1) deletion

---

Problem:

P380 O(1) Time insertion、Delete and get random element

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

I originally thought that getRandom only needed equal probability, but this problem’s testing likely sets a random seed. If you don’t call rand() to generate the order, it will definitely differ from the expected answer.
This problem mainly uses a hashmap to store val->index, and a vector for random access. For insertion, directly append to the end of the vector. For deletion, swap the element to be deleted with the last element, then pop_back(). Remember to update the index of the last element in the hashmap due to the swap.

#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()];
        }
};