C++ 50m solution, beats 97%


  • 0
    C

    First, I studied the solution of 380. Insert Delete GetRandom O(1) using vector and unordered_map<int,int>. The concept is the same with the addition of index mapping for duplicates.

    class RandomizedCollection {
        unordered_map<int, vector<int>> dict;//key val;value array_idx
        vector<pair<int,int>> index;//val; duplicate_idx
    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) {
            dict[val].push_back((int) index.size());
            index.push_back({val,dict[val].size()-1});
            return dict[val].size() == 1;
        }
    
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            if (dict[val].size()) {
                index[dict[val].back()] = index.back();//assignment for pair before the last pair gets poped
                dict[index.back().first][index.back().second] = dict[val].back();//update our dict
                index.pop_back();
                dict[val].pop_back();
                return true;
            }
            return false;
        }
    
        /** Get a random element from the collection. */
        int getRandom() {
            return index[rand() % index.size()].first;
        }
    };

Log in to reply
 

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