LeetCode 380: Insert Delete GetRandom O(1) (Array + Hash Map Index Swap Trick)
LeetCode 380DesignHash TableArrayToday we solve LeetCode 380 - Insert Delete GetRandom O(1).
Source: https://leetcode.com/problems/insert-delete-getrandom-o1/
English
Problem Summary
Design a data structure supporting insert(val), remove(val), and getRandom() in average O(1) time.
Core Idea
Use two structures together: a dynamic array nums for random access, and a hash map idx mapping value to its index in nums. For deletion, swap the target with the last element, then pop.
Why Swap-With-Last Works
Directly deleting from the middle of an array is O(n). Swapping with the last element avoids shifting. After swap, update the moved value's index in the map, then remove last entry.
Algorithm Steps
1) insert(val): if exists in idx, return false; else append to nums, store index in idx.
2) remove(val): if absent, return false; else get its index i, swap nums[i] with nums[last], update moved value index, pop last, erase val from idx.
3) getRandom(): pick uniform random index in [0, nums.size-1].
Complexity Analysis
Time: average O(1) per operation.
Space: O(n).
Common Pitfalls
- Forgetting to update index of the swapped-in last value.
- Removing map entry before finishing swap bookkeeping.
- Calling getRandom() on empty set (problem guarantees valid calls).
- Non-uniform random due to wrong index range.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class RandomizedSet {
private final List<Integer> nums;
private final Map<Integer, Integer> idx;
private final Random rand;
public RandomizedSet() {
nums = new ArrayList<>();
idx = new HashMap<>();
rand = new Random();
}
public boolean insert(int val) {
if (idx.containsKey(val)) return false;
idx.put(val, nums.size());
nums.add(val);
return true;
}
public boolean remove(int val) {
Integer i = idx.get(val);
if (i == null) return false;
int lastIndex = nums.size() - 1;
int lastVal = nums.get(lastIndex);
nums.set(i, lastVal);
idx.put(lastVal, i);
nums.remove(lastIndex);
idx.remove(val);
return true;
}
public int getRandom() {
return nums.get(rand.nextInt(nums.size()));
}
}type RandomizedSet struct {
nums []int
idx map[int]int
}
func Constructor() RandomizedSet {
rand.Seed(time.Now().UnixNano())
return RandomizedSet{nums: []int{}, idx: map[int]int{}}
}
func (this *RandomizedSet) Insert(val int) bool {
if _, ok := this.idx[val]; ok {
return false
}
this.idx[val] = len(this.nums)
this.nums = append(this.nums, val)
return true
}
func (this *RandomizedSet) Remove(val int) bool {
i, ok := this.idx[val]
if !ok {
return false
}
lastIndex := len(this.nums) - 1
lastVal := this.nums[lastIndex]
this.nums[i] = lastVal
this.idx[lastVal] = i
this.nums = this.nums[:lastIndex]
delete(this.idx, val)
return true
}
func (this *RandomizedSet) GetRandom() int {
return this.nums[rand.Intn(len(this.nums))]
}class RandomizedSet {
private:
vector<int> nums;
unordered_map<int, int> idx;
public:
RandomizedSet() {
srand((unsigned)time(nullptr));
}
bool insert(int val) {
if (idx.count(val)) return false;
idx[val] = (int)nums.size();
nums.push_back(val);
return true;
}
bool remove(int val) {
auto it = idx.find(val);
if (it == idx.end()) return false;
int i = it->second;
int lastIndex = (int)nums.size() - 1;
int lastVal = nums[lastIndex];
nums[i] = lastVal;
idx[lastVal] = i;
nums.pop_back();
idx.erase(val);
return true;
}
int getRandom() {
return nums[rand() % nums.size()];
}
};import random
class RandomizedSet:
def __init__(self):
self.nums = []
self.idx = {}
def insert(self, val: int) -> bool:
if val in self.idx:
return False
self.idx[val] = len(self.nums)
self.nums.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.idx:
return False
i = self.idx[val]
last_val = self.nums[-1]
self.nums[i] = last_val
self.idx[last_val] = i
self.nums.pop()
del self.idx[val]
return True
def getRandom(self) -> int:
return random.choice(self.nums)var RandomizedSet = function() {
this.nums = [];
this.idx = new Map();
};
RandomizedSet.prototype.insert = function(val) {
if (this.idx.has(val)) return false;
this.idx.set(val, this.nums.length);
this.nums.push(val);
return true;
};
RandomizedSet.prototype.remove = function(val) {
if (!this.idx.has(val)) return false;
const i = this.idx.get(val);
const lastIndex = this.nums.length - 1;
const lastVal = this.nums[lastIndex];
this.nums[i] = lastVal;
this.idx.set(lastVal, i);
this.nums.pop();
this.idx.delete(val);
return true;
};
RandomizedSet.prototype.getRandom = function() {
const i = Math.floor(Math.random() * this.nums.length);
return this.nums[i];
};中文
题目概述
设计一个数据结构，支持 insert(val)、remove(val)、getRandom()，并要求平均时间复杂度都为 O(1)。
核心思路
组合使用动态数组 nums 与哈希表 idx（值 -> 下标）。数组负责 getRandom 的均匀随机访问，哈希表负责插入/删除时的 O(1) 定位。
为什么要“与尾元素交换再删除”
数组中间删除会触发整体左移，代价是 O(n)。将目标元素与尾元素交换后，再删除尾部即可避免搬移，从而保持均摊 O(1)。
算法步骤
1）insert(val)：若哈希表已有该值返回 false；否则追加到数组尾部并记录下标。
2）remove(val)：若不存在返回 false；否则取出下标 i，把尾元素换到 i，更新尾元素在哈希表中的下标，随后弹出数组尾部并删除哈希映射。
3）getRandom()：在 [0, nums.size-1] 内等概率取一个随机下标。
复杂度分析
时间复杂度：平均 O(1)。
空间复杂度：O(n)。
常见陷阱
- 交换后忘记更新被换上来元素的下标。
- 提前删除哈希映射，导致后续索引更新丢失。
- 空集合调用 getRandom()（题目保证不会出现）。
- 随机下标范围写错，导致分布不均匀。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class RandomizedSet {
private final List<Integer> nums;
private final Map<Integer, Integer> idx;
private final Random rand;
public RandomizedSet() {
nums = new ArrayList<>();
idx = new HashMap<>();
rand = new Random();
}
public boolean insert(int val) {
if (idx.containsKey(val)) return false;
idx.put(val, nums.size());
nums.add(val);
return true;
}
public boolean remove(int val) {
Integer i = idx.get(val);
if (i == null) return false;
int lastIndex = nums.size() - 1;
int lastVal = nums.get(lastIndex);
nums.set(i, lastVal);
idx.put(lastVal, i);
nums.remove(lastIndex);
idx.remove(val);
return true;
}
public int getRandom() {
return nums.get(rand.nextInt(nums.size()));
}
}type RandomizedSet struct {
nums []int
idx map[int]int
}
func Constructor() RandomizedSet {
rand.Seed(time.Now().UnixNano())
return RandomizedSet{nums: []int{}, idx: map[int]int{}}
}
func (this *RandomizedSet) Insert(val int) bool {
if _, ok := this.idx[val]; ok {
return false
}
this.idx[val] = len(this.nums)
this.nums = append(this.nums, val)
return true
}
func (this *RandomizedSet) Remove(val int) bool {
i, ok := this.idx[val]
if !ok {
return false
}
lastIndex := len(this.nums) - 1
lastVal := this.nums[lastIndex]
this.nums[i] = lastVal
this.idx[lastVal] = i
this.nums = this.nums[:lastIndex]
delete(this.idx, val)
return true
}
func (this *RandomizedSet) GetRandom() int {
return this.nums[rand.Intn(len(this.nums))]
}class RandomizedSet {
private:
vector<int> nums;
unordered_map<int, int> idx;
public:
RandomizedSet() {
srand((unsigned)time(nullptr));
}
bool insert(int val) {
if (idx.count(val)) return false;
idx[val] = (int)nums.size();
nums.push_back(val);
return true;
}
bool remove(int val) {
auto it = idx.find(val);
if (it == idx.end()) return false;
int i = it->second;
int lastIndex = (int)nums.size() - 1;
int lastVal = nums[lastIndex];
nums[i] = lastVal;
idx[lastVal] = i;
nums.pop_back();
idx.erase(val);
return true;
}
int getRandom() {
return nums[rand() % nums.size()];
}
};import random
class RandomizedSet:
def __init__(self):
self.nums = []
self.idx = {}
def insert(self, val: int) -> bool:
if val in self.idx:
return False
self.idx[val] = len(self.nums)
self.nums.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.idx:
return False
i = self.idx[val]
last_val = self.nums[-1]
self.nums[i] = last_val
self.idx[last_val] = i
self.nums.pop()
del self.idx[val]
return True
def getRandom(self) -> int:
return random.choice(self.nums)var RandomizedSet = function() {
this.nums = [];
this.idx = new Map();
};
RandomizedSet.prototype.insert = function(val) {
if (this.idx.has(val)) return false;
this.idx.set(val, this.nums.length);
this.nums.push(val);
return true;
};
RandomizedSet.prototype.remove = function(val) {
if (!this.idx.has(val)) return false;
const i = this.idx.get(val);
const lastIndex = this.nums.length - 1;
const lastVal = this.nums[lastIndex];
this.nums[i] = lastVal;
this.idx.set(lastVal, i);
this.nums.pop();
this.idx.delete(val);
return true;
};
RandomizedSet.prototype.getRandom = function() {
const i = Math.floor(Math.random() * this.nums.length);
return this.nums[i];
};
Comments