C++ solution using unordered_map and vector


  • 1
    S

    Hi all,

    The idea is to keep a vector for picking a random number and hash map (unordered_map in c++) for quick insert / removal. The map keeps the indices in the vector as the value so the corresponding entry in vector can be adjusted in O(1) time.

    class RandomizedSet {
    private:
        unordered_map<int, int> indices; // the value is the index of the key
        vector<int> vals;
    public:
        /** Initialize your data structure here. */
        RandomizedSet() {
            srand((int)time(0));
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        bool insert(int val) {
            unordered_map<int, int>::iterator it = indices.find(val);
            if (it == indices.end())   {
                // add the new value's index
                indices.insert(pair<int, int>(val, vals.size()));
                vals.push_back(val);
                
                return true;
            }
            
            return false;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            unordered_map<int, int>::iterator it = indices.find(val);
            if (it == indices.end())   {
                return false;
            }
            
            // remove val
            int index = it->second;
            vals[index] = vals[vals.size() - 1];
            indices.find(vals[index])->second = index;
            vals.pop_back();
            indices.erase(it);
    
            return true;
        }
        
        /** Get a random element from the set. */
        int getRandom() {
            int pick = rand() % vals.size();
    
            return vals[pick];
        }
    };

  • 0
    D

    I have a similar code as yours. The only difference is I put srand((int)time(0)) in function getRandom() just before using the rand() and it gave me wrong answer. I would like to know why putting srand((int)time(0)) in the constructor corrects the code?


  • 0
    S

    @diane Using the srand((int)time(0)) will, I think, reset the random number sequence with the same seed number, thus, resulting in the same number generated each time.


  • 0
    D

    @sculd I think the seed is based on time(0) which will be different time to time and the several getRandom() functions cannot be executed at the same time, thus the random sequence should be different.


  • 0

    @diane
    Hope this helps:

    http://en.cppreference.com/w/cpp/numeric/random/srand:

    Generally speaking, the pseudo-random number generator should only be seeded once, before any calls to rand(), and the start of the program. It should not be repeatedly seeded, or reseeded every time you wish to generate a new batch of pseudo-random numbers.


  • 0

    @diane said in C++ solution using unordered_map and vector:

    time(0) which will be different time to time and the several getRandom() functions cannot be executed at the same time

    You should really read/check what time does. Surely you don't actually think that getRandom() can't be called several times within one second? One second is very long.


Log in to reply
 

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