Correct C++ Solution (hashmap + 2 vectors): It is not enough to use one hashmap and one vector (one hashmap to record the item and duplicate indexes, one vector to record items).


  • 0
    T

    Many solutions use one vector to save all items, the other hashmap to save the mapping from the item to the duplicate indexes. e. g.
    vector: [10 10 20 20 30 30] (assuming all items are inserted in order.)
    map: item 10 ~ index 0, 1; item 20 ~ index 2, 3; item 30 ~ index 4, 5

    Insertion: simply insert the item into the vector, add the tail index into the hashmap, map[new item].add(new index)
    e. g. insert 10, vector: [10, 10, 20, 20, 30, 30, 10], map will be : item 10 ~ index 0, 1, 6; item 20 ~ index 2, 3; item 30 ~ index 4, 5

    Get Random: simply use random function to get index within [1 - vector length], and return the corresponding item.

    Remove:
    Find the last item of the vector,
    if item is the removed one, then delete,
    if NOT, first find the removed item index, since there are duplicates, choose the last duplicate index(It is safe and fine to remove any duplicate), set the item at this position to be the last item, then remove the last item of vector.

    e.g. remove 10, then find last item is 30, the 10's last duplicate index is 1, change the vector:
    [10, 30, 20, 20, 30, 30], remove the last : [10, 30, 20, 20, 30]

    Then change the last item's last duplicate's index to be the removed item's index:

    e.g. map of 30 is 30 ~(4, 5), will becomes 30~(4, 1)

    Finally remove the removed item's index:

    e.g. map of 10 is 10~(0, 1), will becomes 10~(0).

    It seems working very well. However, it is incorrect for some cases when the vector has same duplicates at the tail of the vector, and the user keeps removing elements. Check the example again, after removing 10, the vector becomes:
    [10, 30, 20, 20, 30]
    the map becomes:
    10~(0), 20~(2, 3), 30~(4, 1)

    Remove 10 again, firstly find the last item 30, and moves it from last to the removed item position:
    vector: [30, 30, 20, 20, 30], then remove last item, [30, 30, 20, 20], and change the last item 30's index, which will be 30~(4, 0).

    Now there is a problem that we are supposed to change (4, 1) to be (0, 1), now it is (4, 0), Some posts claim that it is totally fine with the wrong indexes, how about keep removing 30? The wrong index 4 will lead to illegal visit out of the vector range.

    We need to use one more index vector to save the mapping from the item index to the duplicate index. It is named with Index vector.

    e. g.
    vector: [10 10 20 20 30 30]
    map: item 10 ~ (0, 1); item 20 ~ (2, 3); item 30 ~ (4, 5)
    index vector: [ 0 1 0 1 0 1], the first value is 0, means that item 10 corresponds the first duplicate index of map[10]

    Now when removing, the last index in index vector will be used to locate which duplicate in the map will be changed.

    e. g.
    Recall the remove example, to remove 10, find the last item 30, find the last item index 1, then change the vector and remove last: [10 30 20 20 30],
    locate the map[30]~(4, 5), since last item index is 1, then change 5 to the removed item index 1, it becomes
    30 ~(4, 1), don't forget to change the index vector to be [0, 1, 0, 1, 0]

    Remove 10 again, the vector is now [30, 30, 20, 20],
    locate the map[30]~(4, 1), since last item index is 0, then change the first duplicate 4 to be the removed item index 0, which is 30~(0, 1), also update the index vector to be [0, 1, 0, 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) {
        nums.push_back(val);
        m[val].push_back(nums.size() - 1);
        idxs.push_back(m[val].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();
        int lastidx = idxs.back();
        if(val != last) {   // Reduce redundant access.
            nums[m[val].back()] = last;
            idxs[m[val].back()] = lastidx;
            m[last][lastidx] = m[val].back();
        }
        m[val].pop_back();
        nums.pop_back();
        idxs.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()];
    }
    
    unordered_map<int, vector<int>> m;
    vector<int> nums;
    vector<int> idxs;
    

    };


Log in to reply
 

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