C++Vector and 2 Hash Tables to reuse removed locations and save memory for larger tests


  • 0
    F

    To keep the vector from growing every time a the same number is added and removed, I use a second hash map to keep track of if the number has appeared before. The randomizer has to check if the index is valid or not, but, it should still average out to around O(1) and keep memory from growing like crazy. I also start the vector at index 1 to allow using the hash maps default 0 setting as an empty flag.

    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(notEmpty[val] == 1) return false;
            
            if(indices[val] > 0){
                notEmpty[val] = 1;
                return true;
            }
            ++nEntered;
            if(data.size() <= nEntered) data.resize((nEntered)*2);
            data[nEntered] = val;
            indices[val] = nEntered;
            notEmpty[val] = 1;
            
            return true;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            if(notEmpty[val] == 0) return false;
            notEmpty[val] = 0;
            return true;
            
        }
        
        /** Get a random element from the set. */
        int getRandom() {
            int ix = (rand() % nEntered) + 1;
            while(notEmpty[data[ix]] == 0) ix = (rand() % nEntered) + 1;
            return data[ix];
        }
        unordered_map<int, int> indices;
        unordered_map<int, int> notEmpty;
        vector<int> data;
        int nEntered = 0;
    };
    
    /**
     * 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.