题目描述:设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。
insert(val):当元素 val 不存在时,向集合中插入该项。
remove(val):元素 val 存在时,从集合中移除该项。
getRandom:随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
代码实现
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
| class RandomizedSet { private List<Integer> array; private Map<Integer, Integer> valToIndex;
public RandomizedSet() { this.array = new ArrayList<>(); this.valToIndex = new HashMap<>(); }
public boolean insert(int val) { if (this.valToIndex.containsKey(val)) { return false; } this.array.add(val); this.valToIndex.put(val, this.array.size() - 1); return true; }
public boolean remove(int val) { if (!this.valToIndex.containsKey(val)) { return false; } int idx = this.valToIndex.get(val); int tmp = this.array.get(idx); this.array.set(idx, this.array.get(this.array.size() - 1)); this.valToIndex.put(this.array.get(idx), idx); this.array.set(this.array.size() - 1, tmp); this.array.remove(this.array.size() - 1); this.valToIndex.remove(val); return true; }
public int getRandom() { Random random = new Random(); int index = random.nextInt(this.array.size()); return this.array.get(index); } }
|