C++ AC Solution with unordered_map and vector (104ms)


  • 2
    Y

    The main idea is use unordered_map<int, vector<int>> to record multiple location of numbers, and use vector<int> to store all numbers. The main different with problem Insert Delete GetRandom O(1) is :

    1. [insert] We should always push number, no matter the number is existing or not.
    2. [delete] We can erase the number from hashmap only when all the number are removed. (we can get this info by checking the length hashmap[val])

    Besides, the if statement in delete() can reduce redundant access to unordered_map and vector, which can slightly improve its performance.

    If you have any suggestion, please leave the comment. Thanks. :)

    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) {
            nums.push_back(val);
            m[val].push_back(nums.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())  return false;
            int last = nums.back();
            if(val != last) {   // Reduce redundant access.
                nums[m[val].back()] = last;
                m[last].back() = m[val].back();
            }
            m[val].pop_back();
            nums.pop_back();
            if(m[val].size() == 0)
                m.erase(val);
            return true;
        }
        
        /** Get a random element from the collection. */
        int getRandom() {
            return nums[rand() % nums.size()];
        }
    
    private:
        unordered_map<int, vector<int>> m;
        vector<int> nums;
    };
    

  • 0
    F

    Hi, I have a little question. If the number is insert like this: ......5......4, 4. If you wanna delete 5, then the array will be ......4......4, 5 first, and you delete 5 from the end, which makes the array to ......4......4. But in the map, the last index of 4 would become the index of the first 4 instead of the second 4. This time, when you want to delete something, you will exchange the index of first 4 and the deleted element, this will make the whole vector after the first 4 move 1 step forward. Basically, this makes the operation not O(1). I'm not familiar with C++, don't know if the vector will work this way. Thanks.


  • 0
    Y

    @fightingagain The default behavior of my implementation is to use last number to overwrite the target number by nums[m[val].back()] = last;and then pop_back() the number vector. For the hashmap, I will update the new location of last number by m[last].back() = m[val].back(); and pop_back() the useless location, which means I will only use the later location of last number. (in your case, I will update the index of latter 4, rather than the first one.)


  • 0
    F

    I prefer to use a vector instead of a set to implement this question, but this part is exactly where I don't understand when I'm writing my code. I'll draw the map:
    ......5......4, 4
    Initially the map would look like this:
    5 -> [3]
    4 -> [10, 11]
    When deleting 5:
    ......4......4, 4 -> I got this from your if block: m[val].back = 3, last = 4.
    Then the map would be:
    4 -> [10, 3]
    5 -> [3] -> m[4].back() should be 11 first, then you update it to m[val].back() which is 3.
    Then, you delete m[5].back() which is 3, which makes the map:
    4 -> [10, 3]
    So at this moment, the last index of 4 would be 3, instead of 10.

    Thanks.


  • 1
    J

    This case fails:

    ["RandomizedCollection","insert","insert","insert","insert","insert","insert","remove","remove","remove","remove","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom"]
    [[],[10],[10],[20],[20],[30],[30],[10],[10],[30],[30],[],[],[],[],[],[],[],[],[],[]]


Log in to reply
 

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