实现 RandomizedSet 类，使其支持 O(1) 时间复杂度的 insert、remove 和 getRandom。
解析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| var RandomizedSet = function () { this.list = []; this.map = new Map(); };
RandomizedSet.prototype.insert = function (val) {
if (this.map.has(val)) return false;
this.map.set(val, this.list.length);
this.list.push(val);
return true;
};
RandomizedSet.prototype.remove = function (val) {
if (!this.map.has(val)) return false;
const idx = this.map.get(val);
const last = this.list[this.list.length - 1];
this.list[idx] = last;
this.map.set(last, idx);
this.list.pop();
this.map.delete(val);
return true;
};
RandomizedSet.prototype.getRandom = function () {
return this.list[Math.floor(Math.random() * this.list.length)];
};
|