15 lines concise and easy understand c++ solution, vector + unordered_map


  • 0
    A
    class RandomizedSet {
    private:
        vector<int> nums;
        unordered_map<int, int> map;
    public:
        /** Initialize your data structure here. */
        RandomizedSet() {
        }
        
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        bool insert(int val) {
            if(map.count(val)) return false;
            nums.push_back(val);
            map[val] = nums.size() - 1;
            return true;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        bool remove(int val) {
            if(map.count(val) == 0) return false;
            int index = map[val];
            swap(nums[index], nums[nums.size() - 1]);
            nums.pop_back();
            map[nums[index]] = index;
            map.erase(val);
            return true;
        }
        
        /** Get a random element from the set. */
        int getRandom() {
            int index = rand() % nums.size();
            return nums[index];
        }
    };
    
    /**
     * Your RandomizedSet object will be instantiated and called as such:
     * RandomizedSet obj = new RandomizedSet();
     * bool param_1 = obj.insert(val);
     * bool param_2 = obj.remove(val);
     * int param_3 = obj.getRandom();
     */
    

  • 0
    C

    Better use iterator to remove a map element. Using value will take logarithmic time.

        unordered_map<int, int>::iterator it = map.find(val);
        map.erase(it);

  • 0
    A

    @chi Why is that? Especially when each key is unique.

    by position (1)
    iterator erase ( const_iterator position );
    by key (2)
    size_type erase ( const key_type& k );
    range (3)
    iterator erase ( const_iterator first, const_iterator last );

    Complexity
    Average case: Linear in the number of elements removed (which is constant for versions (1) and (2)).
    Worst case: Linear in the container size.


Log in to reply
 

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