Sharing my C++ solution with explanation (swap and pop when remove())


  • 0

    Idea is to use two data structures to do book-keeping:

    1. unordered_map<int, int> to store <number-to-index> relationship
    2. vector<int> to store <index-to-number> relationship
    3. You can use the size from map or vector to determine how many elements are there but I tend to use a explicit member variable "size" to record as we are designing a new data structure.
    • insert():
      simply add to map and push_back to vector
      increment size
    • getRandom():
      generate a random integer randIdx from 0 to size - 1, and simply return the element at index randIdx (from the vector)
    • remove():
      swap the element to be removed with the last element in the vector
      pop out the last element
      update book-keeping information in both data structures
      decrement size

    code in cpp:

    class RandomizedSet {
        unordered_map<int, int> index; // map of num to its index in nums array
        vector<int> nums; // storing the actual numbers inserted
        int size;
        
    public:
        /** Initialize your data structure here. */
        RandomizedSet() : size(0) {
            /* initialize random seed: */
            srand (time(NULL));
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        bool insert(int val) {
            if (index.find(val) != index.end())
                return false;
                
            nums.push_back(val);
            index[val] = size ++;
            return true;s
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            if (index.find(val) == index.end())
                return false;
            
            int back = nums.back();
            int backIdx = index[back];
            
            int delIdx = index[val];
            
            swap(nums[backIdx], nums[delIdx]); // swap with last element in nums
            nums.pop_back();
            
            index[back] = delIdx; // update last element's index in map
            index.erase(val); // erase val entry from map
            
            size --;
            
            return true;
        }
        
        /** Get a random element from the set. */
        int getRandom() {
            if (size <= 0) return -1; // should be an exception
            
            /* generate secret number between 0 and size - 1: */
            int randIdx = rand() % size;
            
            return nums[randIdx];
        }
    };
    

Log in to reply
 

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