C++ solution using unordered_map and vector


  • 0
    P

    The basic idea is to keep track of all the elements in a compact vector, while the unordered_map stores the mappings between the elements of the set and their corresponding indices of the vector.
    If we remove a value from the set, we can swap the value with the last one in the vector, just like what we will do to remove the biggest or smallest element from a heap.

    class RandomizedSet {
    public:
        /** Initialize your data structure here. */
        RandomizedSet() {}
    
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        bool insert(int val) {
            if (m.find(val) != m.end()) {
                return false;
            }
    
            v.push_back(val);
            m[val] = v.size() - 1;
    
            return true;
        }
    
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            auto &&it = m.find(val);
            if (it == m.end()) {
                return false;
            }
    
            auto index = it->second;
            if (index != v.size() - 1) {
                auto key = v.back();
                m[key] = index;
                v[index] = key;
            }
    
            m.erase(it);
            v.pop_back();
    
            return true;
        }
    
        /** Get a random element from the set. */
        int getRandom() {
            return v[rand() % v.size()];
        }
    
    private:
    
        unordered_map<int, size_t> m;
        vector<int> v;
    };
    
    /**
     * Your RandomizedSet object will be instantiated and called as such:
     * RandomizedSet obj = new RandomizedSet();
     * bool param_1 = obj.insert(val);
     * bool param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();
     */
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.