代碼訓練(23)LeetCode之隨機訪問元素

Author: Once Day Date: 2025年6月5日

漫漫長路，才剛剛開始…

全系列文章可參考專欄: 十年代碼訓練_Once-Day的博客-CSDN博客

參考文章:

• 380. O(1) 時間插入、刪除和獲取隨機元素 - 力扣（LeetCode）
• 力扣 (LeetCode) 全球極客摯愛的技術成長平臺

1. 原題

實現RandomizedSet 類：

• RandomizedSet() 初始化 RandomizedSet 對象
• bool insert(int val) 當元素 val 不存在時，向集合中插入該項，并返回 true ；否則，返回 false 。
• bool remove(int val) 當元素 val 存在時，從集合中移除該項，并返回 true ；否則，返回 false 。
• int getRandom() 隨機返回現有集合中的一項（測試用例保證調用此方法時集合中至少存在一個元素）。每個元素應該有 相同的概率 被返回。

你必須實現類的所有函數，并滿足每個函數的 平均 時間復雜度為 O(1) 。

提示：

• -231 <= val <= 231 - 1
• 最多調用 insert、remove 和 getRandom 函數 2 * ``105 次
• 在調用 getRandom 方法時，數據結構中 至少存在一個 元素。

示例 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 。

2. 分析

題目要求實現一個 RandomizedSet 類，該類包含以下方法：

1. RandomizedSet() - 初始化對象。
2. bool insert(int val) - 插入元素 val，如果元素不存在則插入并返回 true，否則返回 false。
3. bool remove(int val) - 移除元素 val，如果元素存在則移除并返回 true，否則返回 false。
4. int getRandom() - 隨機返回集合中的一個元素。保證調用時集合中至少有一個元素，且每個元素有相同的被返回概率。

要求所有操作的平均時間復雜度為 O(1)。

為了滿足該題目的要求，我們可以使用哈希表和數組組合的數據結構：

1. 數組：用于存儲元素，支持 O(1) 時間復雜度的隨機訪問。
2. 哈希表：鍵為元素值，值為該元素在數組中的索引，支持 O(1) 時間復雜度的插入和刪除操作。

方法實現細節：

插入 (insert):

• 檢查哈希表中是否已存在該元素。如果存在，返回 false。
• 將元素添加到數組末尾，并在哈希表中記錄該元素的索引。
• 返回 true。

刪除 (remove):

• 檢查哈希表中是否存在該元素。如果不存在，返回 false。
• 從數組中移除該元素，為了維持 O(1) 的復雜度，可以將數組最后一個元素移動到被刪除元素的位置，并更新哈希表。
• 從哈希表中刪除該元素，并更新數組的大小。
• 返回 true。

獲取隨機元素 (getRandom):

• 從數組中隨機選擇一個索引，然后返回該索引對應的元素。

性能優化關鍵點:

• 內存管理：合理分配和釋放內存是關鍵，尤其是在 randomizedSetCreate 和 randomizedSetFree 函數中。
• 哈希沖突：避免哈希沖突可以提升性能，因此選擇合適的哈希函數和沖突解決機制很重要。

3. 代碼實現

struct entry {int val;int idx;struct entry* next;
};typedef struct {int size;                  // 當前元素數量int array[200000];         // 動態數組存儲元素struct entry* map[100000]; // 哈希表存儲元素到索引的映射
} RandomizedSet;RandomizedSet* randomizedSetCreate() {RandomizedSet* set = malloc(sizeof(RandomizedSet));memset(set, 0x0, sizeof(RandomizedSet));srand(time(NULL)); // 初始化隨機種子return set;
}bool randomizedSetInsert(RandomizedSet* set, int val) {int key = val % 100000;struct entry** prev = &(set->map[key]);struct entry* item = set->map[key];while (item != NULL) {if (item->val == val) {return false;}prev = &(item->next);item = item->next;}item = malloc(sizeof(struct entry));item->val = val;item->next = NULL;item->idx = set->size;*prev = item;set->array[set->size] = val;set->size++;return true;
}bool randomizedSetRemove(RandomizedSet* set, int val) {int key = val % 100000;struct entry** prev = &(set->map[key]);struct entry* item = set->map[key];while (item != NULL) {if (item->val == val) {break;}prev = &(item->next);item = item->next;}if (item == NULL) {return false;}*prev = item->next;int idx = item->idx;free(item);if (idx == set->size - 1) {set->size--;return true;}int lastElement = set->array[set->size - 1];set->array[idx] = lastElement; // 將最后一個元素移動到被刪除元素的位置set->size--;key = lastElement % 100000;item = set->map[key];while (item != NULL) {if (item->val == lastElement) {break;}item = item->next;}item->idx = idx;return true;
}int randomizedSetGetRandom(RandomizedSet* set) {int randomIndex = rand() % set->size;return set->array[randomIndex];
}void randomizedSetFree(RandomizedSet* set) {for (int i = 0; i < 100000; i++) {struct entry* item = set->map[i];while (item != NULL) {struct entry* temp = item->next;free(item);item = temp;}}free(set);
}

這段代碼實現了一個 RandomizedSet 結構，它支持插入、刪除、隨機訪問和銷毀操作。下面分析每部分代碼的功能和設計邏輯。

使用了兩種數據結構：

• 數組 (array)：用于存儲元素值，支持快速通過索引訪問和隨機訪問。
• 哈希表 (map)：鏈地址法解決哈希沖突的哈希表，存儲鍵為元素值，值為該元素在數組中的索引。

分配內存并初始化 RandomizedSet，其中 memset 用于初始化內存區域。

插入操作首先計算哈希鍵值，然后遍歷鏈表檢查元素是否已存在。如果不存在，創建新條目并加入鏈表和數組。

刪除操作查找鏈表中的元素，然后從鏈表和數組中刪除，同時更新相關元素的索引。

通過隨機生成索引來從數組中獲取元素。

釋放哈希表中所有鏈表的內存以及 RandomizedSet 結構的內存。

4. 總結

這個題目主要考察數據結構的靈活應用和操作的優化。通過綜合利用數組和哈希表，我們能夠實現各種操作的平均 O(1) 時間復雜度。對于提升編程能力，重點是掌握各種數據結構的特點及其適用場景，以及如何根據需求選擇和設計最合適的數據結構。

表和數組中刪除，同時更新相關元素的索引。

通過隨機生成索引來從數組中獲取元素。

釋放哈希表中所有鏈表的內存以及 RandomizedSet 結構的內存。