C++ unordered_multimap and vector solution


  • 1
    W

    Use multimap so we could store value pair with same key. The place it needs to pay attention is when we update the index of vector for removed element in the multimap, we need to make sure we update the last node of the vector in the multimap.

    class RandomizedCollection {
    public:
        /** Initialize your data structure here. */
        RandomizedCollection() {
            
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            bool ret = true;
            if(valToIndexMap.find(val) != valToIndexMap.end())
                ret = false;
            
            vals.push_back(val);
            valToIndexMap.insert(pair<int,int>(val, vals.size()-1));
            
            return ret;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            auto removeItemIt = valToIndexMap.find(val);
    
    		if (removeItemIt == valToIndexMap.end())
    			return false;
    
    		int removeItemIndex = removeItemIt->second;
    		auto replaceItemItRange = valToIndexMap.equal_range(vals[vals.size() - 1]);
    		unordered_multimap<int, int>::iterator replaceItemIt = replaceItemItRange.first;
    		for (auto it = replaceItemItRange.first; it != replaceItemItRange.second; it++){
    			if (it->second > replaceItemIt->second){
    				replaceItemIt = it;
    			}
    		}
    		replaceItemIt->second = removeItemIndex;
    		swap(vals[vals.size() - 1], vals[removeItemIndex]);
    
    		vals.pop_back();
    		valToIndexMap.erase(removeItemIt);
    
    		return true;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            int retIndex = rand() % vals.size();
            return vals[retIndex];
        }
        
    private:
        unordered_multimap<int, int> valToIndexMap;
        vector<int> vals;
    };
    

  • 1
    G

    I thought of the same solution. The only reservation about this solution is that it might not be O(1) if you have a single value that appears N times (and only that value). Then you will have to scan through your map for the right index to delete, which will be O(N).


Log in to reply
 

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