Design a data structure that supports all following operations in averageO(1) time.
Note: Duplicate elements are allowed.
insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
// Init an empty collection. RandomizedCollection collection = new RandomizedCollection();
// Inserts 1 to the collection. Returns true as the collection did not contain 1. collection.insert(1);
// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1]. collection.insert(1);
// Inserts 2 to the collection, returns true. Collection now contains [1,1,2]. collection.insert(2);
// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3. collection.getRandom();
// Removes 1 from the collection, returns true. Collection now contains [1,2]. collection.remove(1);
// getRandom should return 1 and 2 both equally likely. collection.getRandom();
分析
这题紧接上一题 380. Insert Delete GetRandom O(1),但要求允许插入重复值。由于允许插入重复值,哈希表的结构应该是 value-list 这样的对应关系,其中 list 记录的是数组中的索引值,插入,删除的逻辑大致一样,但我们需要有一个方法可以从数组中找到哈希表的列表中的某个值,因此需要记录哈希表中 list 的索引,因此引入 Element 数据结构,除了保存本身的值外,还记录哈希表中 list 的索引,这样就能找到数组和 Map 的对应关系了。
/** Initialize your data structure here. */ publicRandomizedCollection(){ this.elementList = new ArrayList<Element>(); this.hashIndexListMap = new HashMap<Integer, List<Integer>>(); this.size = 0; } /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ publicbooleaninsert(int val){ List<Integer> indexList = this.hashIndexListMap.getOrDefault(val, new ArrayList<>()); this.elementList.add(new Element(val, indexList.size())); indexList.add(this.size); this.hashIndexListMap.put(val, indexList); this.size++; return indexList.size() == 1; } /** Removes a value from the collection. Returns true if the collection contained the specified element. */ publicbooleanremove(int val){ List<Integer> indexList = this.hashIndexListMap.get(val); if (indexList == null) { returnfalse; } int elementIndex = indexList.get(indexList.size() - 1); Element lastElement = this.elementList.get(this.elementList.size() - 1); List<Integer> lastElementIndexList = this.hashIndexListMap.get(lastElement.value); lastElementIndexList.set(lastElement.index, elementIndex); this.elementList.set(elementIndex, lastElement); this.elementList.remove(this.elementList.size() - 1); indexList.remove(indexList.size() - 1); if (indexList.isEmpty()) { this.hashIndexListMap.remove(val); } this.size--; returntrue; } /** Get a random element from the collection. */ publicintgetRandom(){ returnthis.elementList.get(rand.nextInt(this.elementList.size())).value; } }
classElement{ int value; int index; Element(int value, int index) { this.value = value; this.index = index; } }
/** * Your RandomizedCollection object will be instantiated and called as such: * RandomizedCollection obj = new RandomizedCollection(); * boolean param_1 = obj.insert(val); * boolean param_2 = obj.remove(val); * int param_3 = obj.getRandom(); */