JavaScript Solution


  • 0
    S
    /**
     * Initialize your data structure here.
     */
    var RandomizedSet = function() {
        this.set = [];
    };
    
    /**
     * Inserts a value to the set. Returns true if the set did not already contain the specified element. 
     * @param {number} val
     * @return {boolean}
     */
    RandomizedSet.prototype.insert = function(val) {
        if (this.set.indexOf(val) >= 0) {
            return false;
        }
        this.set.push(val);
        return true;
    
    };
    
    /**
     * Removes a value from the set. Returns true if the set contained the specified element. 
     * @param {number} val
     * @return {boolean}
     */
    RandomizedSet.prototype.remove = function(val) {
        var index = this.set.indexOf(val);
        if (index < 0) {
            return false;
        }
        this.set.splice(index, 1);
        return true;
    
    };
    
    /**
     * Get a random element from the set.
     * @return {number}
     */
    RandomizedSet.prototype.getRandom = function() {
        var l = this.set.length;
        return this.set[random(l)];
    
        function random(l) {
            return Math.floor((Math.random() * l));
        }
    };
    
    /** 
     * Your RandomizedSet object will be instantiated and called as such:
     * var obj = Object.create(RandomizedSet).createNew()
     * var param_1 = obj.insert(val)
     * var param_2 = obj.remove(val)
     * var param_3 = obj.getRandom()
     */
    

  • 0
    S

    @shao Is set.splice() a O(1) operation? I thought it should be O(n)? Please correct me if I am wrong.


  • 0
    S

    @swissashley Yeah, you are right, the splice is O(n), but I found this one is the fastest way so far, I also tried to implement it using an object, which is way too slow than using an array.
    Need some time to investigating the new JavaScript 'set'. Any suggestion?


Log in to reply
 

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