AC 86ms C++ solution using unordered_map and list with detailed explanation can pass newly added test cases!


  • 0
    J

    Share my thinking process:

    • O(1) getRandom --> need a vector to keep track of all numbers;
    • O(1) remove/insert --> hash table to keep track of the numbers;

    But what should be the value for the hash table?

    Why do not we use the indices of the key in the vector as the value?

    So we have: hash: number --> its indices in the number vectors

    Therefore, we have hash map:
    unordered_map<int, list<int> > hash;

    Each number has a bucket of its indices.

    Follow the similar thought as the previous question, we can start coding.

    But there is one issue, if we are replacing the duplicates, which one should we choose? We can certainly choose the last one in the bucket. But if the same duplicate is removed again, can we still choose the last one in the bucket? The answer is no!!! That is the place where I found out my previous code is wrong for the additional test cases.

    How to fix that? Just think about the LRU. The last position in the bucket is the least use one, going to replace it at coming new element. For each newly added index, we should place it in the begin of the list (bucket).

    class RandomizedCollection {
    private:
        vector<int> m_nums;
        unordered_map<int, list<int> > m_hash;
        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) {
            m_hash[val].push_back(m_nums.size());
            m_nums.push_back(val);
            
            return m_hash[val].size() == 1;
        }
        
        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        bool remove(int val) {
            list<int> & bucket = m_hash[val];
            bool found = !bucket.empty();
            if(found){
                int last = m_nums.back();m_nums.pop_back(); // replace with the last one in the m_nums
                int pos = bucket.back();bucket.pop_back(); // get the pos of the val being evicted
                if(last != val){
                    m_nums[pos] = last;
                    m_hash[last].insert(m_hash[last].begin(), pos);  
                    // LRU! always put the new replaced index in the front of bucket!
                    m_hash[last].pop_back();
                }
            }
            return found;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            if(m_nums.empty())  return INT_MIN;
            return m_nums[rand() % m_nums.size()];
        }
    };

Log in to reply
 

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