百度360必应搜狗淘宝本站头条
mqtt服务器xftp6mybatiscollectionkeyerrorc#var
当前位置：网站首页 > 热门文章 > 正文

LeetCode 力扣官方题解 | 380. O(1) 时间插入、删除和获取随机元素

bigegpt 2025-03-18 19:58 4 浏览

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 nums;
    Map indices;
    Random random;


    public RandomizedSet() {
        nums = new ArrayList();
        indices = new HashMap();
        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 nums;
    Dictionary indices;
    Random random;


    public RandomizedSet() {
        nums = new List();
        indices = new Dictionary();
        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 nums;
    unordered_map 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 /

本文作者：力扣

声明：本文归“力扣”版权所有，如需转载请联系。

相关推荐

【机器学习】数据挖掘神器LightGBM详解(附代码)

来源：机器学习初学者本文约11000字，建议阅读20分钟本文为你介绍数据挖掘神器LightGBM。LightGBM是微软开发的boosting集成模型，和XGBoost一样是对GBDT...

3分钟，用DeepSeek全自动生成语音计算器，还带括号表达式!

最近，大家慢慢了解到了DeepSeek的强大功能，特别是它在编程领域也同样强大。编程零基础小白，一行代码不用写，也能全自动生成一个完整的、可运行的软件来！很多程序员一直不相信小白不写代码也能编软件！下...

python学习笔记 3.表达式

在Python中，表达式是由值、变量和运算符组成的组合。以下是一些常见的Python表达式：算术表达式：由数值和算术运算符组成的表达式，如加减乘除等。例如：5+3、7*2、10/3等。字符...

5.7 VS 8.x，为什么用户不升级MySql

一般来说为了更好的功能和性能，都需要将软件升级到最新的版本，然而在开源软件中，由于一些开发商变化或其他的问题（开源授权变化），致使人们不愿使用最新的版本，一个最典型的问题就是CentOS操作系统。还有...

大厂高频:讲一下MySQL主从复制

大家经常听说主从复制，那么主从复制的意义？能解决的问题有哪些？主从复制能解决的问题就是在我们平时开发的程序中操作数据库的时候，大多数的情况查询的操作大大超过了写的操作，也就说对数据库读取数据的压力比较...

MYSQL数据库的五大安全防护措施

以技术为基础的企业里最有价值的资产莫过于是客户或者其数据库中的产品信息了。因此，在这样的企业中，保证数据库免受外界攻击是数据库管理的重要环节。很多数据库管理员并没有实施什么数据库保护措施，只是因为觉得...

docker安装mysql

准备工作已安装Docker环境（官方安装文档）终端/命令行工具（Linux/macOS/WSL）步骤1：拉取MySQL镜像打开终端执行以下命令，拉取官方MySQL镜像（默认最新版本）：d...

Zabbix监控系统系列之六:监控 mysql

zabbix监控mysql1、监控规划在创建监控项之前要尽量考虑清楚要监控什么，怎么监控，监控数据如何存储，监控数据如何展现，如何处理报警等。要进行监控的系统规划需要对Zabbix很了解，这里只是...

详解MySQL的配置文件及优化

#头条创作挑战赛#在Windows系统中，MySQL服务器启动时最先读取的是my.ini这个配置文件。在Linux系统中，配置文件为my.cnf，其路径一般为/etc/my.cnf或/etc/mysq...

Mysql 几个批处理执行脚本

学习mysql过程中，需要创建测试数据，并让多人每人一个数据库连接并进行作业检查。整合部分批处理创建数据批量创建数据库DELIMITER$CREATEPROCEDURECreateDatab...

MySQL学到什么程度?才有可以在简历上写精通

前言如今互联网行业用的最多就是MySQL，然而对于高级Web面试者，尤其对于寻找30k下工作的求职者，很多MySQL相关知识点基本都会涉及，如果面试中，你的相关知识答的模糊和不切要点，基...

mysql 主、从服务器配置“Slave_IO_Running: Connecting” 问题分析

#在进行mysql主、从服务器配置时，”SHOWSLAVESTATUS;“查看从库状态Slave_IO_Runing，出现错误：“Slave_IO_Running:Connectin...

MYSQL数据同步

java开发工程师在实际的开发经常会需要实现两台不同机器上的MySQL数据库的数据同步，要解决这个问题不难，无非就是mysql数据库的数据同步问题。但要看你是一次性的数据同步需求，还是定时数据同步，亦...

「MySQL 8」MySQL 5.7都即将停只维护了，是时候学习一波MySQL 8了

MySQL8新特性选择MySQL8的背景：MySQL5.6已经停止版本更新了，对于MySQL5.7版本，其将于2023年10月31日停止支持。后续官方将不再进行后续的代码维护。另外，...

Prometheus监控mysql

通过Prometheus监控Mysql，我们需要在Mysql端安装一个mysql-exporter，然后Prometheus通过mysql-exporter暴露的端口抓取数据。1.安装一个MYSQL配...

一周热门
最近发表
标签列表