My c++ solution, easy to understand.


  • 0
    B
    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) 
        {
            mNums.push_back(val);
            LUT[val].push_back(mNums.size() - 1);
            return LUT[val].size() == 1;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val)
        {
            if(LUT[val].size() != 0) 
            {
                int idx = LUT[val].back();
                //Put the last number in the position of idx and delete the last element.
                mNums[idx] = mNums[mNums.size() - 1];
                mNums.pop_back();
                //Update LUT.
                LUT[mNums[idx]].back() = idx;
                LUT[val].pop_back();
                return true;
            }
            return false;
        }
        
        /** Get a random element from the collection. */
        int getRandom()
        {
            return mNums[rand() % mNums.size()];
        }
        
    private:
        vector<int> mNums;
        map<int, vector<int>> LUT;
    };
    

  • 0

    Hi, BigMonkey. Consider the following case:

    insert(1);
    insert(2);
    insert(2);
    remove(1);
    remove(2);
    remove(2);
    

    The index should be out of range when deleting the last '2'.


Log in to reply
 

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