381. Insert Delete GetRandom O(1) - Duplicates allowed

Difficulty:
Related Topics:
Similar Questions:

Problem

RandomizedCollection is a data structure that contains a collection of numbers, possibly duplicates (i.e., a multiset). It should support inserting and removing specific elements and also reporting a random element.

Implement the RandomizedCollection class:

You must implement the functions of the class such that each function works on average O(1) time complexity.

Note: The test cases are generated such that getRandom will only be called if there is at least one item in the RandomizedCollection.

  Example 1:

Input
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
Output
[null, true, false, true, 2, true, 1]

Explanation
RandomizedCollection randomizedCollection = new RandomizedCollection();
randomizedCollection.insert(1);   // return true since the collection does not contain 1.
                                  // Inserts 1 into the collection.
randomizedCollection.insert(1);   // return false since the collection contains 1.
                                  // Inserts another 1 into the collection. Collection now contains [1,1].
randomizedCollection.insert(2);   // return true since the collection does not contain 2.
                                  // Inserts 2 into the collection. Collection now contains [1,1,2].
randomizedCollection.getRandom(); // getRandom should:
                                  // - return 1 with probability 2/3, or
                                  // - return 2 with probability 1/3.
randomizedCollection.remove(1);   // return true since the collection contains 1.
                                  // Removes 1 from the collection. Collection now contains [1,2].
randomizedCollection.getRandom(); // getRandom should return 1 or 2, both equally likely.

  Constraints:

Solution


var RandomizedCollection = function() {
    this.map = {};
    this.arr = [];
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.insert = function(val) {
    var notFound = this.map[val] === undefined;
    if (notFound) this.map[val] = { arr: [], map: {} };
    this.map[val].map[this.arr.length] = this.map[val].arr.length;
    this.map[val].arr.push(this.arr.length);
    this.arr.push(val);
    return notFound;
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.remove = function(val) {
    if (this.map[val] === undefined) return false;
    var valIndexs = this.map[val].arr;
    var delIndex = valIndexs[valIndexs.length - 1];
    var lastValue = this.arr.pop();
    if (valIndexs.length === 1) {
        delete this.map[val];
    } else {
        valIndexs.pop();
        delete this.map[val].map[delIndex];
    }
    if (lastValue !== val) {
        var lastValueIndex = this.map[lastValue].map[this.arr.length];
        this.map[lastValue].arr[lastValueIndex] = delIndex;
        delete this.map[lastValue].map[this.arr.length];
        this.map[lastValue].map[delIndex] = lastValueIndex;
        this.arr[delIndex] = lastValue;
    }
    return true;
};

/**
 * @return {number}
 */
RandomizedCollection.prototype.getRandom = function() {
    var num = Math.floor(Math.random() * this.arr.length);
    return this.arr[num];
};

/** 
 * Your RandomizedCollection object will be instantiated and called as such:
 * var obj = new RandomizedCollection()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

Explain:

nope.

Complexity: