一、題目分析

（一）功能需求

我們需要實現 RandomizedSet 類，包含以下功能：

• RandomizedSet()：初始化數據結構。
• bool insert(int val)：當元素 val 不存在時，插入該元素并返回 true；若已存在，返回 false 。
• bool remove(int val)：當元素 val 存在時，移除該元素并返回 true；若不存在，返回 false 。
• int getRandom()：隨機返回現有集合中的一個元素，每個元素被返回的概率相同，且調用時集合至少有一個元素 。

（二）核心挑戰

要讓插入、刪除、獲取隨機元素操作的平均時間復雜度都達到 O(1) 。常規的數據結構往往難以單獨滿足這些要求，比如哈希表雖能高效插入和刪除，但難以高效隨機獲取；動態數組便于隨機獲取，但插入和刪除（尤其是中間元素）的時間復雜度較高。所以需要結合兩者的優勢來實現。

二、算法思想：哈希表 + 動態數組的協同運用

（一）哈希表（Map）的作用

使用 Map<Integer, Integer> 來存儲元素 val 以及它在動態數組中的索引。這樣可以：

• 插入元素時，快速判斷元素是否已存在（通過 map.containsKey(val) ），時間復雜度為 O(1) 。
• 刪除元素時，快速獲取元素在動態數組中的位置，為后續在動態數組中高效刪除元素做準備，時間復雜度為 O(1) 。

（二）動態數組（List）的作用

使用 List 來存儲元素的值，方便進行隨機獲取操作。因為要實現隨機獲取元素且每個元素概率相同，我們可以利用 Random 類生成隨機索引（范圍是 0 到 list.size() - 1 ），然后通過 list.get(randomIndex) 快速獲取元素，時間復雜度為 O(1) 。

（三）刪除操作的優化

刪除元素時，直接刪除動態數組中間的元素時間復雜度會是 O(n) （需要移動元素 ）。為了優化這個操作，我們采用“交換刪除”的策略：

1. 獲取要刪除元素 val 在動態數組中的索引 reNumIndex ，以及動態數組最后一個元素 lastNum 。
2. 將動態數組中 reNumIndex 位置的元素替換為 lastNum 。
3. 更新 lastNum 在哈希表中的索引為 reNumIndex 。
4. 刪除動態數組的最后一個元素（時間復雜度 O(1) ），并從哈希表中移除 val 。這樣就將刪除操作的時間復雜度優化到了 O(1) 。

三、代碼實現與詳細注釋

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;class RandomizedSet {// 哈希表，鍵為元素值，值為該元素在 numsList 中的索引Map<Integer, Integer> map; // 動態數組，存儲元素的值，用于隨機獲取List<Integer> numsList; // 用于生成隨機索引Random random; // 構造函數，初始化數據結構public RandomizedSet() {map = new HashMap<>();numsList = new ArrayList<>();random = new Random();}// 插入元素操作public boolean insert(int val) {// 判斷元素是否已存在于哈希表中if (map.containsKey(val)) { return false; // 已存在，返回 false} else {// 將元素 val 與它在 numsList 中的索引（當前 numsList 的長度，因為即將添加到末尾）存入哈希表map.put(val, numsList.size()); // 將元素添加到 numsList 末尾numsList.add(val); return true; // 插入成功，返回 true}}// 刪除元素操作public boolean remove(int val) {// 判斷元素是否存在于哈希表中if (map.containsKey(val)) { // 獲取動態數組最后一個元素的值int lastNum = numsList.get(numsList.size() - 1); // 獲取要刪除元素 val 在 numsList 中的索引int reNumIndex = map.get(val); // 將 numsList 中 reNumIndex 位置的元素替換為 lastNumnumsList.set(reNumIndex, lastNum); // 更新 lastNum 在哈希表中的索引為 reNumIndexmap.put(lastNum, reNumIndex); // 刪除 numsList 的最后一個元素（時間復雜度 O(1) ）numsList.remove(numsList.size() - 1); // 從哈希表中移除要刪除的元素 valmap.remove(val); return true; // 刪除成功，返回 true} else {return false; // 元素不存在，返回 false}}// 隨機獲取元素操作public int getRandom() {// 生成一個 0 到 numsList.size() - 1 范圍內的隨機索引int randomIndex = random.nextInt(numsList.size()); // 根據隨機索引獲取元素并返回return numsList.get(randomIndex); }
}/*** Your RandomizedSet object will be instantiated and called as such:* RandomizedSet obj = new RandomizedSet();* boolean param_1 = obj.insert(val);* boolean param_2 = obj.remove(val);* int param_3 = obj.getRandom();*/

四、復雜度分析

（一）時間復雜度

• 插入操作（insert）：主要操作是哈希表的 containsKey 和 put ，以及動態數組的 add 操作。哈希表的這兩個操作時間復雜度是 O(1) ，動態數組 add 操作（在末尾添加）時間復雜度也是 O(1) ，所以插入操作平均時間復雜度為 O(1) 。
• 刪除操作（remove）：通過“交換刪除”的優化，哈希表的 containsKey、get、put、remove 操作，以及動態數組的 get、set、remove（末尾刪除 ）操作，時間復雜度都是 O(1) ，所以刪除操作平均時間復雜度為 O(1) 。
• 隨機獲取操作（getRandom）：生成隨機索引和動態數組的 get 操作時間復雜度都是 O(1) ，所以該操作平均時間復雜度為 O(1) 。

（二）空間復雜度

哈希表存儲了 n 個元素（n 是集合中元素的數量 ），空間復雜度為 O(n) ；動態數組也存儲了 n 個元素，空間復雜度為 O(n) ；Random 類占用常數空間。所以總的空間復雜度為 O(n) ，n 是集合中元素的最大數量。

O(1) 時間插入、刪除和獲取隨機元素這道題，通過巧妙結合哈希表和動態數組，充分發揮了兩者的優勢，成功實現了插入、刪除、隨機獲取操作平均時間復雜度為 O(1) 的需求。其中刪除操作的“交換刪除”策略，更是優化時間復雜度的關鍵。