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)