c++ solution with map and vector


  • 0
    W
    class RandomizedCollection {
    public:
        map<int, vector<int>> dict;
        vector<int> array;
    
        /** Initialize your data structure here. */
        RandomizedCollection() {
            srand(time(0));
        }
        
        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        bool insert(int val) {
            array.push_back(val);
            int idx = array.size() - 1;
            bool ret = dict[val].empty();
            dict[val].push_back(idx);
            return ret;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            if (dict[val].empty()) {
                return false;
            } else {
                int idx = dict[val].back();
                dict[val].pop_back();
                if (idx < array.size() - 1) {
                    int last = array.back();
                    dict[last].pop_back();
                    dict[last].push_back(idx);
                    array[idx] = last;
                }
                array.pop_back();
                return true;
            }
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            int idx = rand() % array.size();
            return array[idx];
        }
    
    };
    

Log in to reply
 

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