Design a data structure that supports all following operations in average O(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.
Example:
// 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();
Solution:
參考http://zxi.mytechroad.com/blog/hashtable/leetcode-381-insert-delete-getrandom-o1-duplicates-allowed/
-
思路與#380類似蕉汪，但不同在于有重復(fù)的數(shù)字笛洛。所以需要用
HashMap<Integer, List<Integer>>和List<Node>兩個數(shù)據(jù)結(jié)構(gòu)。-
HashMap： 用于存儲每個數(shù)字，和其在List中的Index -
Node：An object,val ~ number,indexInMap ~ 當(dāng)前數(shù)字在Map的List<Integer>中對應(yīng)的Index -
List<Node>： 數(shù)字node的list
image.png
-
Insert：需要向List<Node>中加入node，同時更新Mapremove: 難點！琳要！ 同樣也是與尾部的number交換，然后移除到尾部的數(shù)字秤茅。難點在于update index in map for last elementgetRandom: 與#380相同稚补。
//3. update index in map for the last element
numberVsIndexes.get(lastEntry.val).set (lastEntry.indexInMap, removeIndex);
class RandomizedCollection {
class Node {
public int val;
public int indexInMap;
public Node (int val, int index) {
this.val = val;
this.indexInMap = index;
}
}
Map<Integer, List<Integer>> numberVsIndexes;
List<Node> nodeList;
/** Initialize your data structure here. */
public RandomizedCollection() {
numberVsIndexes = new HashMap<Integer, List<Integer>> ();
nodeList = new ArrayList<Node> ();
}
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public boolean insert(int val) {
boolean result = false;
if (!numberVsIndexes.containsKey (val)) {
result = true;
}
int indexInNodeList = nodeList.size ();
List<Integer> indexes = numberVsIndexes.getOrDefault (val, new ArrayList<Integer> ());
indexes.add (indexInNodeList);
numberVsIndexes.put (val, indexes);
int indexInMap = indexes.size () - 1;
Node node = new Node (val, indexInMap);
nodeList.add (node);
return result;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
if (!numberVsIndexes.containsKey (val)) {
return false;
}
//1. get the last entry of the remove number
List<Integer> removeCandidates = numberVsIndexes.get (val);
int removeIndex = removeCandidates.get (removeCandidates.size () - 1);
//2. get the last entry of the nodeList
Node lastEntry = nodeList.get (nodeList.size () - 1);
//3. update index in map for the last element
numberVsIndexes.get(lastEntry.val).set (lastEntry.indexInMap, removeIndex);
//3. swap
nodeList.set (removeIndex, lastEntry);
//4. clean up the map
nodeList.remove (nodeList.size () - 1);
removeCandidates.remove (removeCandidates.size () - 1);
if (removeCandidates.size () == 0) {
numberVsIndexes.remove (val);
}
return true;
}
/** Get a random element from the collection. */
public int getRandom() {
Random rand = new Random ();
return nodeList.get (rand.nextInt (nodeList.size ())).val;
}
}
/**
* 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();
*/
