一、題目大意
實作RandomizedSet 類：
- RandomizedSet() 初始化 RandomizedSet 物件
- bool insert(int val) 當元素 val 不存在時，向集合中插入該項，并回傳 true ；否則，回傳 false ，
- bool remove(int val) 當元素 val 存在時，從集合中移除該項，并回傳 true ；否則，回傳 false ，
- int getRandom() 隨機回傳現有集合中的一項（測驗用例保證呼叫此方法時集合中至少存在一個元素），每個元素應該有 相同的概率 被回傳，
你必須實作類的所有函式，并滿足每個函式的 平均 時間復雜度為 O(1) ，
示例：
輸入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
輸出
[null, true, false, true, 2, true, false, 2]
解釋
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 ，回傳 true 表示 1 被成功地插入，
randomizedSet.remove(2); // 回傳 false ，表示集合中不存在 2 ，
randomizedSet.insert(2); // 向集合中插入 2 ，回傳 true ，集合現在包含 [1,2] ，
randomizedSet.getRandom(); // getRandom 應隨機回傳 1 或 2 ，
randomizedSet.remove(1); // 從集合中移除 1 ，回傳 true ，集合現在包含 [2] ，
randomizedSet.insert(2); // 2 已在集合中，所以回傳 false ，
randomizedSet.getRandom(); // 由于 2 是集合中唯一的數字，getRandom 總是回傳 2 ，
提示：
- -231 <= val <= 231 - 1
- 最多呼叫 insert、remove 和 getRandom 函式 2 * 105 次
- 在呼叫 getRandom 方法時，資料結構中 至少存在一個 元素，
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/insert-delete-getrandom-o1
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
這道題有個限制在常數時間范圍內實作插入洗掉和獲得亂數操作，沒有該限制的話直接用一個HashSet就可以搞定，我們利用一個可變list和一個HashMap，其中list用來保存數字，HashMap用來建立每個數字和其在list中的位置之間的映射，重點在于洗掉元素的邏輯，如果要洗掉的元素不存在回傳false，如果存在，先求出該元素在list中的索引，將list中最后一個元素更新到此位置，同時更新該元素中在hashmap的索引，然后list中洗掉最后一個元素，hashmap也洗掉要洗掉的元素 ，
三、解題方法
3.1 Java實作
class RandomizedSet {
List<Integer> nums;
Map<Integer, Integer> indices;
Random random;
public RandomizedSet() {
nums = new ArrayList<>();
indices = new HashMap<>();
random = new Random();
}
public boolean insert(int val) {
if (indices.containsKey(val)) {
return false;
}
// 為什么不寫成indices.put(val, nums.size());
int index = nums.size();
nums.add(val);
indices.put(val, index);
return true;
}
public boolean remove(int val) {
if (!indices.containsKey(val)) {
return false;
}
int index = indices.get(val);
int last = nums.get(nums.size() - 1);
nums.set(index, last);
indices.put(last, index);
nums.remove(nums.size() - 1);
indices.remove(val);
return true;
}
public int getRandom() {
return nums.get(random.nextInt(nums.size()));
}
}
四、總結小記
- 2022/10/18 今天有點不順哦，倒霉的事一個接著一個，想想好事，想想明天，心里就舒坦了
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/517609.html
標籤：其他
下一篇：Linux生成亂數