Simple C++ Solution


  • 0
    L

    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) {
        v.push_back(val);
        m[val].push_back(v.size()-1);
        return m[val].size()==1;
    }
    
    /** 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()||m[val].size()==0)
            return false;
        int rm = m[val].back();
        int last_val = v.back();
        m[last_val].back() = rm;
        v[rm] = last_val;
        m[val].pop_back();
        v.pop_back();
        return true;
    }
    
    /** Get a random element from the collection. */
    int getRandom() {
        return v[rand()%v.size()];
    }
    

    private:
    vector<int> v;
    unordered_map<int, vector<int>> m;
    };


Log in to reply
 

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