C++ 45ms easy solution with only hash


  • 0
    Y

    Idea is very easy, we have two hash tables. One is responsible to map a value to index while another one is to map index to value. I swap the element deleted to the end of idx before delete it. In this way, the index is always 0 ~ n -1 and we can easily make a random get to them.

    class RandomizedSet {
    public:
        /** Initialize your data structure here. */
        unordered_map<int, int> valToIdxs;
        unordered_map<int, int> idxToVals;
        int n = 0; // current size
        RandomizedSet() {
            valToIdxs.clear();
            idxToVals.clear();
            n = 0;
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        bool insert(int val) {
            if (valToIdxs.count(val) == 0) {
                valToIdxs[val] = n;
                idxToVals[n++] = val;
                return true;
            }
            return false;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            if (valToIdxs.count(val) > 0) {
                int idx = valToIdxs[val];
                int last = n - 1;
                
                valToIdxs[idxToVals[last]] = idx;
                idxToVals[idx] = idxToVals[last]; // change idx of last element to idx
                
                valToIdxs.erase(valToIdxs.find(val));
                idxToVals.erase(idxToVals.find(last));
                n --;
                return true;
            }
            return false;
        }
        
        /** Get a random element from the set. */
        int getRandom() {
            int idx = rand() % n;
            return idxToVals[idx];
        }
    };
    
    

Log in to reply
 

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