Interview Classic 150 Questions P380 O(1) Time Insert, Delete, and Get Random Element

---

Timeline

Timeline

2025-10-04

init

Hash table, vector O(1) deletion

---

Title:

P380 O(1) Time Insert、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 for getRandom, as long as the probability is the same, it’s fine. However, this problem’s test likely sets a random seed. If you don’t call rand(), the order will definitely differ from the answer.
This problem mainly uses a hashmap to store val, index, and a vector for random access. When inserting, directly put it at the end of the vector. When deleting, 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()];
        }
};