leetcode381. Insert Delete GetRandom O(1) - Duplicates allowed
摘要：
題目要求
Design a data structure that supports all following operations in average O(1) time.
Note: Duplicate elements are allowed.
insert(val): Ins...
題目要求
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();
設計一個數據結構，支援能夠在O(1)的時間內完成對數字的插入，刪除和獲取隨機數的操作，允許插入重複的數字，同時要求每個數字被隨機獲取的概率和該數字當前在資料結構中的個數成正比。
強烈建議先看一下這個問題的基礎版本，傳送門在這裡。
思路和程式碼
遵循之前基礎版本的思路，當解決這種問題的時候我們會用陣列和hashmap來做位置的儲存，從而更新的時候無需檢索。但是在這題的情境下，存在一個問題，舉個例子：
假如現在插入1,2,3,3,4,3,3
此時的map中應當是如下：
1:[0] 2:[1] 3:[2,3,5,6] 4:[4]
我們先執行刪除1，按照之前的規則，我們會刪除陣列中最後一個元素，並將其值移動到這個位置上map應當被更新為
2:[1] 3:[2,3,5,0] 4:[4]
接著我們再刪除2，此時雖然最後一個元素還是3，但是這個3在位置陣列中的位置卻是需要O(n)的時間來查詢的，這就違反了O(1)的刪除時間複雜度。
網上有一些java實現採用OrderSet來解決，這是不合理的。因為有序堆本質上底層是一個最大堆或最小堆，它的插入和刪除操作都需要O(lgn)的時間複雜度來完成
這裡我們採用的方式是繼續冗餘，即我們在插入每一個元素的時候，同時記錄該元素在下標陣列中的位置，舉個例子：
先插入1，則map的值為[1:[0]]
，list的值為[[1,0]]
此處的0代表1這個值在下標陣列[0]中位於第0個位置上。
[1:[0], 2:[1]]
, list的值為[[1,0],[2,0]]
再插入1，此時map=
[1:[0, 2], 2:[1]
, list的值為[[1,0],[2,0],[1,1]]
此時刪除2，同理，我們還是會將陣列中最後一個元素的值替換在刪除掉元素的位置，此處我們從map中得出2最後一次在陣列中出現的下標為1，我們需要將最後位置上的1替換掉當前2的值，之後我們還能從陣列中得知，1這個數字它對應的位置下標的索引為2，因此我們再將map[1]
中map[1][2]
的值替換為2所在的新的位置，即1。此時的map=[1:[0, 1], 2:[]
list=[[1,0], [1,1]]
程式碼如下：
public class InsertDeleteGetRandomDuplicatesallowed_381 {
private List<Pair> list;
private Map<Integer, List<Integer>> index;
/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
public InsertDeleteGetRandomDuplicatesallowed_381() {
list = new ArrayList<>();
index = new HashMap<>();
}
public boolean insert(int val) {
boolean contains = true;
if(!index.containsKey(val) || index.get(val).isEmpty()) {
contains = false;
}
List<Integer> tmp = index.getOrDefault(val, new ArrayList<>());
tmp.add(list.size());
index.put(val, tmp);
list.add(new Pair(val,tmp.size()-1));
return !contains;
}
/** Removes a value from the collection. Returns true if the collection contained the specified element. */
public boolean remove(int val) {
if(!index.containsKey(val) || index.get(val).isEmpty()) {
return false;
}
List<Integer> tmp = index.get(val);
int position = tmp.remove(tmp.size()-1);
if(position != list.size()-1) {
Pair lastPair = list.get(list.size()-1);
int lastValue = lastPair.value;
List<Integer> lastValuePositions = index.get(lastValue);
lastValuePositions.set(lastPair.position, position);
list.set(position, lastPair);
}
list.remove(list.size()-1);
return true;
}
/** Get a random element from the collection. */
public int getRandom() {
int position = (int)Math.floor((Math.random() * list.size()));
return list.get(position).value;
}
public static class Pair{
int value;
int position;
public Pair(int value, int position) {
this.value = value;
this.position = position;
}
}
}