-
Notifications
You must be signed in to change notification settings - Fork 0
/
381-InsertDeleteGetRandomO(1)-Duplicatesallowed.js
58 lines (55 loc) · 1.42 KB
/
381-InsertDeleteGetRandomO(1)-Duplicatesallowed.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
* Initialize your data structure here.
*/
var RandomizedCollection = function () {
this.idx = new Map();
this.nums = [];
};
/**
* Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedCollection.prototype.insert = function (val) {
this.nums.push(val);
const set = this.idx.has(val) ? this.idx.get(val) : new Set();
set.add(this.nums.length - 1);
this.idx.set(val, set);
return set.size === 1;
};
/**
* Removes a value from the collection. Returns true if the collection contained the specified element.
* @param {number} val
* @return {boolean}
*/
RandomizedCollection.prototype.remove = function (val) {
if (!this.idx.has(val)) {
return false;
}
let i = undefined;
for (const it of this.idx.get(val)) {
if (!i) {
i = it;
break;
}
}
const lastNum = this.nums[this.nums.length - 1];
this.nums[i] = lastNum;
this.idx.get(val).delete(i);
this.idx.get(lastNum).delete(this.nums.length - 1);
if (i < this.nums.length - 1) {
this.idx.get(lastNum).add(i);
}
if (this.idx.get(val).size === 0) {
this.idx.delete(val);
}
this.nums.pop();
return true;
};
/**
* Get a random element from the collection.
* @return {number}
*/
RandomizedCollection.prototype.getRandom = function () {
return this.nums[Math.floor(Math.random() * this.nums.length)];
};