設計一個支持在平均時間復雜度 O(1) 下， 執行以下操作的資料結構，注意：允許出現重復元素，
insert(val)：向集合中插入元素 valremove(val)：當 val 存在時，從集合中移除一個 valgetRandom()：從現有集合中隨機獲取一個元素，每個元素被回傳的概率應該與其在集合中的數量呈線性相關
示例
// 初始化一個空的集合，
RandomizedCollection collection = new RandomizedCollection();
// 向集合中插入 1 ，回傳 true 表示集合不包含 1 ，
collection.insert(1);
// 向集合中插入另一個 1 ，回傳 false 表示集合包含 1 ，集合現在包含 [1,1] ，
collection.insert(1);
// 向集合中插入 2 ，回傳 true ，集合現在包含 [1,1,2] ，
collection.insert(2);
// getRandom 應當有 2/3 的概率回傳 1 ，1/3 的概率回傳 2 ，
collection.getRandom();
// 從集合中洗掉 1 ，回傳 true ，集合現在包含 [1,2] ，
collection.remove(1);
// getRandom 應有相同概率回傳 1 和 2 ，
collection.getRandom();
解題思路
用 List 存放元素，再用 Map 來記錄每個元素在 List 中的所有下標，按照這個思想，實作插入和獲取亂數都不難，唯獨洗掉操作會卡殼，每次洗掉時不需要真的從 List 中將元素刪掉，只要用 List 中的最后一個元素覆寫待洗掉元素，在 Map 中修改最后一個元素的下標即可，需要注意的是，每次洗掉操作后，List 的后段會有無效的部分，因為每次執行洗掉操作后，有效部分的最后一個元素就變成無效了，所以要多加注意
class RandomizedCollection {
// 存放元素
private List<Integer> list;
// 記錄每個元素在 list 中的所有下標
private Map<Integer, List<Integer>> map;
// 執行過的有效 remove 數
private int removeCount;
/** Initialize your data structure here. */
public RandomizedCollection() {
list = new ArrayList<>();
map = new HashMap<>();
removeCount = 0;
}
public boolean insert(int val) {
boolean flag;
// removeCount == 0，直接在 list 后追加元素
if(removeCount == 0) {
list.add(val);
} else {
// 否則要在 list 的有效范圍內追加元素，由洗掉操作思想可知，list 末尾的部分元素是無效的
list.add(list.size() - removeCount, val);
}
// 是否已有重復元素存在
if(map.containsKey(val)) {
flag = false;
map.get(val).add(list.size() - 1);
} else {
flag = true;
List<Integer> indexList = new LinkedList<>();
indexList.add(list.size() - 1);
map.put(val, indexList);
}
return flag;
}
public boolean remove(int val) {
boolean flag;
// 元素存在并且對應的下標記錄數不為 0
if(map.containsKey(val) && map.get(val).size() != 0) {
flag = true;
// 取出第一個元素所在的下標并用 index 保存
int index = map.get(val).get(0);
// 從 indexList 中洗掉第一個下標
map.get(val).remove(0);
// 獲取最后一個有效元素
int lastVal = list.get(list.size() - 1 - removeCount);
// lastVal 覆寫 index 處的值（從 list 中洗掉一個 val）
list.set(index, lastVal);
// 獲取 lastVal 所在的所有下標
List<Integer> tempList = map.get(lastVal);
// 遍歷 tempList，找到原本所處的 list 有效范圍末尾的下標，用 index 替代
for(int i = 0; i < tempList.size(); i++) {
if(tempList.get(i) == (list.size() - 1 - removeCount)) {
map.get(lastVal).set(i, index);
break;
}
}
removeCount++;
} else {
flag = false;
}
return flag;
}
public int getRandom() {
int randomNum = new Random().nextInt(list.size() - removeCount);
return list.get(randomNum);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/205090.html
標籤：其他
上一篇：服務器基礎知識