Re: [閒聊] 每日LeetCode已回收
380. Insert Delete GetRandom O(1)
設計一個Set資料結構，支援以下操作：
insert(int val)：若元素不存在插入元素並返回true，否則false。
remove(int val)：若元素存在則移除元素並返回true，否則false。
getRandom()：從set終獲取一個隨機數，時間複雜度必須是O(1)。
Example：
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove",
"insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
思路：
1.用一個HashMap儲存插入元素的索引，一個List儲存元素本身，插入的時候記錄兩者。
2.刪除元素的時候如果直接根據索引從List移除元素需要O(n)時間，而且還要一併修改
map的索引值，我們改為把要被刪除的元素和List的最後一個元素交換位置並刪除最後
一個元素，這樣只需要O(1)的時間。
remove(3) 交換元素並更新map(4)索引 移除最後一個元素
1 2 3 4 => 1 2 4 3 => 1 2 4
3.直接從List的隨機索引取一個數字，這樣取隨機數就只需要O(1)時間了。
JavaCode：
----------------------------------------------
class RandomizedSet {
private HashMap<Integer, Integer> valueIndexMap;
private List<Integer> valuesList;
private Random rand;
public RandomizedSet() {
valueIndexMap = new HashMap<>();
valuesList = new ArrayList<>();
rand = new Random();
}
public boolean insert(int val) {
if (valueIndexMap.containsKey(val)) {
return false;
}
valuesList.add(val);
valueIndexMap.put(val, valuesList.size() - 1);
return true;
}
public boolean remove(int val) {
if (!valueIndexMap.containsKey(val)) {
return false;
}
int valuesIdx = valueIndexMap.get(val);
int lastElement = valuesList.get(valuesList.size() - 1);
valuesList.set(valuesIdx, lastElement);
valueIndexMap.put(lastElement, valuesIdx);
valuesList.remove(valuesList.size() - 1);
valueIndexMap.remove(val);
return true;
}
public int getRandom() {
int randIdx = rand.nextInt(valuesList.size());
return valuesList.get(randIdx);
}
}
----------------------------------------------
--
https://i.imgur.com/YPBHGGE.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.9.105 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1669689731.A.591.html
推
11/29 10:49,
3年前
, 1F
11/29 10:49, 1F
推
11/29 10:50,
3年前
, 2F
11/29 10:50, 2F
討論串 (同標題文章)
完整討論串 (本文為第 121 之 719 篇)：