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. */varRandomizedSet=function(){this.nums=newArray();this.locs=newObject();};/** * 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(!(valinthis.locs)){this.nums.push(val);this.locs[val]=this.nums.length-1;returntrue;}returnfalse;};/** * 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(valinthis.locs){letloc=this.locs[val];letlastEl=this.nums[this.nums.length-1];this.nums[loc]=lastEl;this.locs[lastEl]=loc;this.nums.pop();deletethis.locs[val];returntrue;}returnfalse;};/** * Get a random element from the set. * @return {number} */RandomizedSet.prototype.getRandom=function(){returnthis.nums[Math.floor(Math.random()*this.nums.length)];};Top comments(0)
Subscribe
For further actions, you may consider blocking this person and/orreporting abuse
