Design a data structure that supports all following operations in average O(1) time.
- insert(val): Inserts an item val to the set if not already present.
- remove(val): Removes an item val from the set if present.
- getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Algorithm:
The intuition here is whenever you want to achieve in less time, you have to sacrifice space. So we are gonna use extra space with hash table.
/**
* Initialize your data structure here.
*/
var RandomizedSet = function () {
this.nums = new Array();
this.locs = new Object();
};
/**
* 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 (!(val in this.locs)) {
this.nums.push(val);
this.locs[val] = this.nums.length - 1;
return true;
}
return false;
};
/**
* 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) {
if(val in this.locs) {
let loc = this.locs[val];
let lastEl = this.nums[this.nums.length - 1];
this.nums[loc] = lastEl;
this.locs[lastEl] = loc;
this.nums.pop();
delete this.locs[val];
return true;
}
return false;
};
/**
* Get a random element from the set.
* @return {number}
*/
RandomizedSet.prototype.getRandom = function () {
return this.nums[Math.floor(Math.random() * this.nums.length)];
};
Top comments (0)