C++ 53ms solution using vector, unordered_set and unordered_map


  • 0
    C

    For this problem, insert() and getRandom() are relatively trivial to implement. The tricky part is in the remove() function. In order to have fast "remove" operations, we need to look up the indices that have the same element quickly. unordered_set is a perfect fit to the requirement.

    class RandomizedCollection {
    public:
        /** Initialize your data structure here. */
        RandomizedCollection() {
            
            srand(time(NULL));
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            
            bool newItem = true;
            if (m.find(val) != m.end()) 
                newItem = false;
            nums.emplace_back(val);
            m[val].insert(nums.size()-1);
            return newItem;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            
            if (m.find(val) == m.end()) return false;
            unordered_set<int>::iterator it = m[val].begin();
    
            int indexRemoval = *it;
            m[val].erase(indexRemoval);
            
            if (indexRemoval != nums.size()-1) {
                nums[indexRemoval] = nums[nums.size()-1];
                m[nums[nums.size()-1]].erase(nums.size()-1);
                m[nums[nums.size()-1]].insert(indexRemoval);
            }
            
            nums.pop_back();
    
            if (m[val].empty())
                m.erase(val);
                
            return true;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            
            if (nums.empty()) return -1;
            return nums[rand() % nums.size()];
        }
    
    private:
        vector<int> nums;
        unordered_map<int, unordered_set<int>> m;
    };
    

Log in to reply
 

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