当前位置： 面试刷题>> O(1) 时间插入、删除和获取随机元素(经典算法150题)
### 题目描述
设计一个支持以下操作的数据结构：
1. `Insert(val)`：向数据结构中插入一个元素，如果元素已存在则不进行任何操作。
2. `Remove(val)`：从数据结构中删除一个元素，如果元素不存在则不进行任何操作。
3. `GetRandom()`：随机返回数据结构中的一个元素，每个元素被返回的概率相同。
要求所有操作的时间复杂度均为 O(1)。
### 解题思路
为了满足所有操作的时间复杂度为 O(1)，我们可以使用哈希表（HashMap）来存储元素及其存在性，同时使用一个动态数组（ArrayList 或 List）来存储所有元素的值，以确保能够随机访问。
- **哈希表**：用于快速判断元素是否存在，并实现 O(1) 的插入和删除。
- **动态数组**：用于存储所有元素，通过随机索引实现 O(1) 的随机访问。
### 示例代码
#### PHP 示例
```php
class RandomizedCollection {
private $nums;
private $valMap;
function __construct() {
$this->nums = [];
$this->valMap = [];
}
function insert($val) {
if (!isset($this->valMap[$val])) {
$this->valMap[$val] = [];
}
if (!in_array($val, $this->nums)) {
$this->nums[] = $val;
$this->valMap[$val][] = count($this->nums) - 1;
return true;
}
return false;
}
function remove($val) {
if (!isset($this->valMap[$val]) || empty($this->valMap[$val])) {
return false;
}
$indexToRemove = array_pop($this->valMap[$val]);
$lastVal = end($this->nums);
// Swap with the last element and pop
$this->nums[$indexToRemove] = $lastVal;
array_pop($this->nums);
// Update the index map for the last element
$lastValIndex = array_search($lastVal, $this->valMap[$lastVal]);
$this->valMap[$lastVal][$lastValIndex] = $indexToRemove;
if (empty($this->valMap[$val])) {
unset($this->valMap[$val]);
}
return true;
}
function getRandom() {
$randIndex = array_rand($this->nums);
return $this->nums[$randIndex];
}
}
```
#### Python 示例
```python
import random
class RandomizedCollection:
def __init__(self):
self.nums = []
self.valMap = {}
def insert(self, val: int) -> bool:
if val not in self.valMap:
self.valMap[val] = []
if val not in self.nums:
self.nums.append(val)
self.valMap[val].append(len(self.nums) - 1)
return True
return False
def remove(self, val: int) -> bool:
if val not in self.valMap or not self.valMap[val]:
return False
index_to_remove = self.valMap[val].pop()
last_val = self.nums[-1]
# Swap with the last element and pop
self.nums[index_to_remove] = last_val
self.nums.pop()
# Update the index map for the last element
if last_val in self.valMap:
last_val_index = self.valMap[last_val].index(len(self.nums))
self.valMap[last_val][last_val_index] = index_to_remove
if not self.valMap[val]:
del self.valMap[val]
return True
def getRandom(self) -> int:
return random.choice(self.nums)
```
#### JavaScript 示例
```javascript
class RandomizedCollection {
constructor() {
this.nums = [];
this.valMap = new Map();
}
insert(val) {
if (!this.valMap.has(val)) {
this.valMap.set(val, []);
}
if (!this.nums.includes(val)) {
this.nums.push(val);
this.valMap.get(val).push(this.nums.length - 1);
return true;
}
return false;
}
remove(val) {
if (!this.valMap.has(val) || this.valMap.get(val).length === 0) {
return false;
}
const indexToRemove = this.valMap.get(val).pop();
const lastVal = this.nums[this.nums.length - 1];
// Swap with the last element and pop
this.nums[indexToRemove] = lastVal;
this.nums.pop();
// Update the index map for the last element
if (this.valMap.has(lastVal)) {
const lastIndex = this.valMap.get(lastVal).findIndex(idx => idx === this.nums.length);
this.valMap.get(lastVal)[lastIndex] = indexToRemove;
}
if (this.valMap.get(val).length === 0) {
this.valMap.delete(val);
}
return true;
}
getRandom() {
const randomIndex = Math.floor(Math.random() * this.nums.length);
return this.nums[randomIndex];
}
}
```
以上代码均实现了题目要求的功能，并且确保了所有操作的时间复杂度为 O(1)。