网站首页 > java教程 正文
380. O(1) 时间插入、删除和获取随机元素
「彭博bloomberg、亚马逊、优步」考题
力扣题解
题目描述
难易度：中等
实现 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 方法时，数据结构中 至少存在一个 元素。
解决方案
方法一：变长数组 + 哈希表
思路与算法
这道题要求实现一个类，满足插入、删除和获取随机元素操作的平均时间复杂度为 O(1)。
变长数组可以在 O(1) 的时间内完成获取随机元素操作，但是由于无法在 O(1) 的时间内判断元素是否存在，因此不能在 O(1) 的时间内完成插入和删除操作。哈希表可以在 O(1) 的时间内完成插入和删除操作，但是由于无法根据下标定位到特定元素，因此不能在 O(1) 的时间内完成获取随机元素操作。为了满足插入、删除和获取随机元素操作的时间复杂度都是 O(1)，需要将变长数组和哈希表结合，变长数组中存储元素，哈希表中存储每个元素在变长数组中的下标。
插入操作时，首先判断 val 是否在哈希表中，如果已经存在则返回 false，如果不存在则插入 val，操作如下：
1.在变长数组的末尾添加 val；
2.在添加 val 之前的变长数组长度为 val 所在下标 index，将 val 和下标 index 存入哈希表；
3.返回true。
删除操作时，首先判断 val 是否在哈希表中，如果不存在则返回 false，如果存在则删除 val，操作如下：
1.从哈希表中获得 val 的下标 index；
2.将变长数组的最后一个元素 last 移动到下标 index 处，在哈希表中将 last 的下标更新为 index；
3.在变长数组中删除最后一个元素，在哈希表中删除 val；
4.返回 true。
删除操作的重点在于将变长数组的最后一个元素移动到待删除元素的下标处，然后删除变长数组的最后一个元素。该操作的时间复杂度是 O(1)，且可以保证在删除操作之后变长数组中的所有元素的下标都连续，方便插入操作和获取随机元素操作。
获取随机元素操作时，由于变长数组中的所有元素的下标都连续，因此随机选取一个下标，返回变长数组中该下标处的元素。
代码
Python3
class RandomizedSet:
def __init__(self):
self.nums = []
self.indices = {}
def insert(self, val: int) -> bool:
if val in self.indices:
return False
self.indices[val] = len(self.nums)
self.nums.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.indices:
return False
id = self.indices[val]
self.nums[id] = self.nums[-1]
self.indices[self.nums[id]] = id
self.nums.pop()
del self.indices[val]
return True
def getRandom(self) -> int:
return choice(self.nums)Java
class RandomizedSet {
List<Integer> nums;
Map<Integer, Integer> indices;
Random random;
public RandomizedSet() {
nums = new ArrayList<Integer>();
indices = new HashMap<Integer, Integer>();
random = new Random();
}
public boolean insert(int val) {
if (indices.containsKey(val)) {
return false;
}
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() {
int randomIndex = random.nextInt(nums.size());
return nums.get(randomIndex);
}
}C#
public class RandomizedSet {
IList<int> nums;
Dictionary<int, int> indices;
Random random;
public RandomizedSet() {
nums = new List<int>();
indices = new Dictionary<int, int>();
random = new Random();
}
public bool Insert(int val) {
if (indices.ContainsKey(val)) {
return false;
}
int index = nums.Count;
nums.Add(val);
indices.Add(val, index);
return true;
}
public bool Remove(int val) {
if (!indices.ContainsKey(val)) {
return false;
}
int index = indices[val];
int last = nums[nums.Count - 1];
nums[index] = last;
indices[last] = index;
nums.RemoveAt(nums.Count - 1);
indices.Remove(val);
return true;
}
public int GetRandom() {
int randomIndex = random.Next(nums.Count);
return nums[randomIndex];
}
}C++
class RandomizedSet {
public:
RandomizedSet() {
srand((unsigned)time(NULL));
}
bool insert(int val) {
if (indices.count(val)) {
return false;
}
int index = nums.size();
nums.emplace_back(val);
indices[val] = index;
return true;
}
bool remove(int val) {
if (!indices.count(val)) {
return false;
}
int index = indices[val];
int last = nums.back();
nums[index] = last;
indices[last] = index;
nums.pop_back();
indices.erase(val);
return true;
}
int getRandom() {
int randomIndex = rand()%nums.size();
return nums[randomIndex];
}
private:
vector<int> nums;
unordered_map<int, int> indices;
};C
#define MAX_NUM_SIZE 10001
typedef struct {
int key;
int val;
UT_hash_handle hh;
} HashItem;
bool findHash(const HashItem ** obj, int key) {
HashItem *pEntry = NULL;
HASH_FIND_INT(*obj, &key, pEntry);
if (NULL != pEntry) {
return true;
}
return false;
}
int getHash(const HashItem ** obj, int key) {
HashItem *pEntry = NULL;
HASH_FIND_INT(*obj, &key, pEntry);
if (NULL == pEntry) {
return -1;
}
return pEntry->val;
}
void insertHash(HashItem ** obj, int key, int val) {
HashItem *pEntry = NULL;
HASH_FIND_INT(*obj, &key, pEntry);
if (NULL != pEntry) {
pEntry->val = val;
} else {
pEntry = (HashItem *)malloc(sizeof(HashItem));
pEntry->key = key;
pEntry->val = val;
HASH_ADD_INT(*obj, key, pEntry);
}
}
bool removeHash(HashItem ** obj, int key) {
HashItem *pEntry = NULL;
HASH_FIND_INT(*obj, &key, pEntry);
if (NULL != pEntry) {
HASH_DEL(*obj, pEntry);
free(pEntry);
}
return true;
}
void freeHash(HashItem ** obj) {
HashItem *curr, *tmp;
HASH_ITER(hh, *obj, curr, tmp) {
HASH_DEL(*obj, curr);
free(curr);
}
}
typedef struct {
int * nums;
int numsSize;
HashItem * indices;
} RandomizedSet;
RandomizedSet* randomizedSetCreate() {
srand((unsigned)time(NULL));
RandomizedSet * obj = (RandomizedSet *)malloc(sizeof(RandomizedSet));
obj->nums = (int *)malloc(sizeof(int) * MAX_NUM_SIZE);
obj->numsSize = 0;
obj->indices = NULL;
return obj;
}
bool randomizedSetInsert(RandomizedSet* obj, int val) {
HashItem *pEntry = NULL;
if (findHash(&obj->indices, val)) {
return false;
}
int index = obj->numsSize;
obj->nums[obj->numsSize++] = val;
insertHash(&obj->indices, val, obj->numsSize - 1);
return true;
}
bool randomizedSetRemove(RandomizedSet* obj, int val) {
if (!findHash(&obj->indices, val)) {
return false;
}
int index = getHash(&obj->indices, val);
int last = obj->nums[obj->numsSize - 1];
obj->nums[index] = last;
insertHash(&obj->indices, last, index);
obj->numsSize--;
removeHash(&obj->indices, val);
return true;
}
int randomizedSetGetRandom(RandomizedSet* obj) {
int randomIndex = rand() % obj->numsSize;
return obj->nums[randomIndex];
}
void randomizedSetFree(RandomizedSet* obj) {
freeHash(&obj->indices);
free(obj->nums);
free(obj);
}Golang
type RandomizedSet struct {
nums []int
indices map[int]int
}
func Constructor() RandomizedSet {
return RandomizedSet{[]int{}, map[int]int{}}
}
func (rs *RandomizedSet) Insert(val int) bool {
if _, ok := rs.indices[val]; ok {
return false
}
rs.indices[val] = len(rs.nums)
rs.nums = append(rs.nums, val)
return true
}
func (rs *RandomizedSet) Remove(val int) bool {
id, ok := rs.indices[val]
if !ok {
return false
}
last := len(rs.nums) - 1
rs.nums[id] = rs.nums[last]
rs.indices[rs.nums[id]] = id
rs.nums = rs.nums[:last]
delete(rs.indices, val)
return true
}
func (rs *RandomizedSet) GetRandom() int {
return rs.nums[rand.Intn(len(rs.nums))]
}JavaScript
var RandomizedSet = function() {
this.nums = [];
this.indices = new Map();
};
RandomizedSet.prototype.insert = function(val) {
if (this.indices.has(val)) {
return false;
}
let index = this.nums.length;
this.nums.push(val);
this.indices.set(val, index);
return true;
};
RandomizedSet.prototype.remove = function(val) {
if (!this.indices.has(val)) {
return false;
}
let id = this.indices.get(val);
this.nums[id] = this.nums[this.nums.length - 1];
this.indices.set(this.nums[id], id);
this.nums.pop();
this.indices.delete(val);
return true;
};
RandomizedSet.prototype.getRandom = function() {
const randomIndex = Math.floor(Math.random() * this.nums.length);
return this.nums[randomIndex];
};复杂度分析
- 时间复杂度：初始化和各项操作的时间复杂度都是 O(1)。
- 空间复杂度：O(n)，其中 n 是集合中的元素个数。存储元素的数组和哈希表需要 O(n) 的空间。
BY /
本文作者：力扣
声明：本文归“力扣”版权所有，如需转载请联系。
猜你喜欢
- 2025-01-24 LeetCode-215-数组中的第K个最大元素
- 2025-01-24 Java笔记六:ArrayList集合的常用方法和添加元素的源码分析
- 2025-01-24 使用C#编写一个示例代码，演示如何访问和修改C#数组中的元素
- 2025-01-24 C# - 操作数组及元素 034（c#实现一个简单的数组处理类）
- 2025-01-24 JavaScript 中搜索数组元素的四种方法
- 2025-01-24 leetcode每日一题之存在重复元素（列表中重复的元素只剩一个）
- 2025-01-24 2024-12-29:查询数组中元素的出现位置。用go语言，给定一个整数
- 2025-01-24 面试 - 为什么foreach中不允许对元素进行add和remove
- 2025-01-24 在PHP8中向数组添加元素-PHP8知识详解
- 2025-01-24 VBA数组自定义增加元素方法（vba数组自定义增加元素方法有哪些）
欢迎 你 发表评论:
- 最近发表
-
- Java常量定义防暴指南:从"杀马特"到"高富帅"的华丽转身
- Java接口设计原则与实践:优雅编程的艺术
- java 包管理、访问修饰符、static/final关键字
- Java工程师的代码规范与最佳实践:优雅代码的艺术
- 编写一个java程序（编写一个Java程序计算并输出1到n的阶乘）
- Mycat的搭建以及配置与启动（mycat部署）
- Weblogic 安装 -“不是有效的 JDK Java 主目录”解决办法
- SpringBoot打包部署解析:jar包的生成和结构
- 《Servlet》第05节:创建第一个Servlet程序(HelloSevlet)
- 你认为最简单的单例模式，东西还挺多
- 标签列表
-
- java反编译工具 (77)
- java反射 (57)
- java接口 (61)
- java随机数 (63)
- java7下载 (59)
- java数据结构 (61)
- java 三目运算符 (65)
- java对象转map (63)
- Java继承 (69)
- java字符串替换 (60)
- 快速排序java (59)
- java并发编程 (58)
- java api文档 (60)
- centos安装java (57)
- java调用webservice接口 (61)
- java深拷贝 (61)
- 工厂模式java (59)
- java代理模式 (59)
- java.lang (57)
- java连接mysql数据库 (67)
- java重载 (68)
- java 循环语句 (66)
- java反序列化 (58)
- java时间函数 (60)
- java是值传递还是引用传递 (62)
本文暂时没有评论，来添加一个吧(●'◡'●)