C++ 79ms solution using map and set with explanation


  • 0
    F

    Inspired by the question with no duplicate allowed.

    An example of running the code:

    1. "insert 1, insert 2, insert 1, insert 3":
      m: 1 => {0, 2}, 2 => {1}, 3 => {3}
      v: [1, 2, 1, 3]
    2. "remove 2"
      m: 1 => {0, 2}, 3 => {1}
      v: [1, 3, 1]
    3. "remove 1"
      m: 1 => {0}, 3 => {1} (for key '1', it's 1 => {2}, then 1 => {}, and finally 1 => {0})
      v: [1, 3] (it's [1(1), 3, 1(2)] -> [1(2), 3, 1(2)] -> [1(2), 3], where 1(1) and 1(2) means first and second 1's in the previous vector [1, 3, 1])
    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 ne = (m.find(val) == m.end());
            v.push_back(val);
            m[val].insert(v.size()-1); // Insert the index of this number to the map
            return ne;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            bool found = (m.find(val) != m.end());
            if (!found) return false;
            int ind = *(m[val].begin()); // The number val has one or more copies in v; get the index of first copy
            m[val].erase(m[val].begin()); // Remove ind from the set
            if (ind < v.size()-1) { // If ind is not last in v
                v[ind] = v.back(); // We want to keep the number at back but remove the number at ind
                // The below two steps update the index of back number from back to ind
                m[v.back()].erase(v.size()-1);
                m[v.back()].insert(ind);
            }
            v.pop_back(); // Remove the duplicated back number
            if (m[val].empty()) m.erase(val); // If val has an empty set, all its copies have been removed from v. Delete it for consistency
            return found;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            return v[(rand()%v.size())];
        }
        
    private:
        /** key: number inserted */
        /** val: a set of indices where key resides in v */
        unordered_map<int, unordered_set<int>> m;
        /** stores number inserted; the indices are stored in m */
        vector<int> v;
    };
    

Log in to reply
 

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