当前位置: 首页 > news >正文

380. O(1) 时间插入、删除和获取随机元素【 力扣(LeetCode) 】

一、题目描述

实现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 。

三、解题思路

  1. 基本思路:
      在插入和删除操作中,都需要先查找元素,查找元素需要 O ( 1 ) \Omicron(1) O(1) 的复杂度,只能考虑散列表,可以使用 map 进行映射;插入比较简单,只要在序列头或者尾插入都是 O ( 1 ) \Omicron(1) O(1) ,删除需要 O ( 1 ) \Omicron(1) O(1) 的话,可以考虑用尾部元素来填充需要被删除的元素;随机查找操作则需要利用元素的下标进行访问,则可以考虑数组,但数组大小固定,所以可以考虑向量 vector ;综上所述,数据结构就考虑 map 与 vector 结合。【类似游标数组的思想】
  2. 具体思路:
    • 初始化:无;
    • 插入元素:判断该元素是否存在,不存在则在 vector 尾部添加元素,同时记录元素的下标和元素值,按 <值,下标> 的映射关系存入 map;
    • 删除元素:判断该元素是否存在,存在则利用 map 得到该元素的下标,对于 vector ,将该下标的元素用最后一个元素填充,然后删除最后一个元素;对于 map ,修改 vector 最后一个元素的映射关系,然后删除要删除的元素的映射关系;
    • 随机查找:利用 rand 生成随机数,对 vector 的大小求余,然后访问对应元素。

四、参考代码

时间复杂度: O ( 1 ) \Omicron(1) O(1)
空间复杂度: O ( n ) \Omicron(n) O(n)

#include <map>
class RandomizedSet {
public:vector<int> index_num;std::map<int,int> num_index;RandomizedSet() {}bool insert(int val) {if(num_index.count(val)){return false;}else{index_num.push_back(val);num_index[val]=index_num.size()-1;return true;}}bool remove(int val) {if(num_index.count(val)==0){return false;}else{int index=num_index[val];int num=index_num[index_num.size()-1];index_num[index]=num;index_num.pop_back();num_index[num]=index;num_index.erase(val);return true;}}int getRandom() {return index_num[rand()%index_num.size()];}
};

相关文章:

380. O(1) 时间插入、删除和获取随机元素【 力扣(LeetCode) 】

一、题目描述 实现RandomizedSet 类&#xff1a; RandomizedSet() 初始化 RandomizedSet 对象bool insert(int val) 当元素 val 不存在时&#xff0c;向集合中插入该项&#xff0c;并返回 true &#xff1b;否则&#xff0c;返回 false 。bool remove(int val) 当元素 val 存…...

【每日刷题】Day91

【每日刷题】Day91 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; &#x1f33c;文章目录&#x1f33c; 1. 面试题 05.07. 配对交换 - 力扣&#xff08;LeetCode&#xff09; 2. 面试题 08.05. 递归乘法 - 力…...

数据库索引的创建和使用

数据库索引数据库的索引可以加快查询速度&#xff0c;原因是索引使用特定的数据结构(B-Tree)对特定的列额外组织存放,加快存储引擎(索引是存储引擎实现)查找记录的速度。索引优化是数据库优化的最重要手段。 如果查询语句使用索引&#xff08;通常是where条件匹配索引)就会利用…...

光流传感器 - 从零开始认识各种传感器【第二十二期】

光流传感器|从零开始认识各种传感器 1、什么是光流传感器 光流传感器是一种用于测量物体相对于周围环境的运动的设备。它通过检测周围光线的变化来计算出物体的运动方向和速度&#xff0c;广泛应用于机器人导航、无人机飞行控制、虚拟现实等领域。 2、光流传感器是如何工作的…...

爬虫:jsonpath模块及腾讯招聘数据获取

目录 jsonpath模块 腾讯招聘数据获取 jsonpath模块 # pip install jsonpath -i https://pypi.tuna.tsinghua.edu.cn/simple import jsonpathdata {"store": {"book":[{"category": "reference","author": "Nigel Ree…...

透明屏幕的显示原理与特点

透明屏幕&#xff0c;特别是透明LED显示屏&#xff0c;以其独特的显示效果和通透性在现代建筑和广告领域中逐渐崭露头角。它既能提供视觉显示&#xff0c;又不影响采光效果&#xff0c;成为建筑立面和商场橱窗等场景的理想选择。那么&#xff0c;透明屏幕的显示原理是什么&…...

[Day 41] 區塊鏈與人工智能的聯動應用:理論、技術與實踐

去中心化金融&#xff08;DeFi&#xff09;是一個利用區塊鏈技術來構建去中心化的金融系統的運動。它旨在通過智能合約和去中心化應用&#xff08;DApps&#xff09;來提供傳統金融系統中的各種服務&#xff0c;如貸款、儲蓄、保險、交易等&#xff0c;而不依賴於中心化的機構。…...

PHP表单验证

PHP 表单验证是确保用户输入数据符合特定要求的关键步骤&#xff0c;它有助于维护数据的完整性和准确性&#xff0c;同时提高应用的安全性。以下是一个详细的 PHP 表单验证教程&#xff1a; 一、表单的创建 首先&#xff0c;你需要在 HTML 文档中创建一个表单。表单包含输入字…...

英文文献翻译软件有哪些?知道这5款工具就够了

对于那些致力于科研、教育或国际业务的人来说&#xff0c;英文文献往往是获取前沿知识的关键。 然而&#xff0c;语言的障碍往往成为一道难以逾越的鸿沟。幸运的是&#xff0c;科技的进步带来了众多翻译工具&#xff0c;它们不仅能够帮助我们理解外语内容&#xff0c;还能直接…...

单线程 和多线程区别,看打印输出1000个数字效果

执⾏过程: 加载func() -> 执⾏main -> 创建⼦线程t -> ⼦线程t启动 -> 执⾏func中的内容 |-> 继续执⾏main from threading import Thread #此线程不用安装自带。T是大写注意哟 def func():for i in range(1000):print(func,i) #定义一个函数打印 if __name__ …...

【问题处理】海康视频websocket代理问题(websocket在业务系统https协议下调用海康ws协议)

简介 本文记录一次海康视频代理websocket 在https业务系统环境下调用海康服务ws协议的问题。 问题描述 起初前端组件展示视频时&#xff0c;业务系统使用的环境是https&#xff0c;此时海康服务调用时&#xff0c;使用的是ws协议&#xff0c;最后前端控制台报错&#xff1a;…...

【面试分享】面试题——redis

一、题目 Redis的数据持久化策略有哪些什么是缓存穿透&#xff0c;怎么解决什么是布隆过滤器什么是缓存击穿&#xff0c;怎么解决什么是缓存雪崩&#xff0c;怎么解决redis双写问题Redis分布式锁如何实现Redis实现分布式锁如何合理的控制锁的有效时长Redis的数据过期策略有哪些…...

GLSL教程 第十三章:综合项目:创建一个完整的渲染场景(一更)

目录 13.1 项目规划和设计 13.1.1 项目目标 13.1.2 设计要求 13.2 实现场景中的光照、材质和纹理 13.2.1 创建基础场景 13.2.2 应用材质和纹理 13.3 集成高级渲染效果和后期处理 13.3.1 阴影映射(Shadow Mapping) 13.3.2 环境光遮蔽(AO) 13.3.3 简单的景深效果(…...

pgvector: 30 倍构建向量嵌入索引

使用 pgvector 为 HNSW 并行构建索引 Postgres 最受欢迎的向量搜索扩展 pgvector 最近实现了并行索引构建功能&#xff0c;这将分层可导航小世界 (HNSW) 索引构建时间显著提高了 30 倍。 祝贺 Andrew Kane 和 pgvector 的贡献者发布此版本&#xff0c;这巩固了 Postgres 作为最…...

GNSS形变监测系统

TH-WY1 GNSS形变监测系统采用扼流圈设计有以下几个优势&#xff1a; 高精度测量&#xff1a;扼流圈是一种高精度的传感器&#xff0c;可以提供非常精确的测量结果。这使得GNSS形变监测系统能够准确地测量结构物的形变变化。 高稳定性&#xff1a;扼流圈设计使得传感器具有良好…...

每天一个数据分析题(四百五十三)- 随机抽样

在进行随机抽样时由于某些原因会产生抽样误差&#xff0c;以下关于抽样误差的说法&#xff0c;正确的是 A. 抽样误差是随机抽样调查中偶然发生的代表性误差 B. 抽样误差的大小同样本单位数成正比关系 C. 简单随机抽样比分层抽样误差大 D. 重复抽样比不重复抽样误差小 数据…...

Python爬虫知识体系-----Selenium

数据科学、数据分析、人工智能必备知识汇总-----Python爬虫-----持续更新&#xff1a;https://blog.csdn.net/grd_java/article/details/140574349 文章目录 一、安装和基本使用二、元素定位三、访问元素信息四、自动化交互五、PhantomJS六、Chrome headless 一、安装和基本使用…...

springboot+webSocket对接chatgpt

webSocket对接参考 话不多说直接上代码 WebSocket package com.student.config;import com.alibaba.fastjson2.JSONArray; import com.alibaba.fastjson2.JSONObject; import lombok.extern.slf4j.Slf4j; import org.springframework.http.MediaType; import org.springfram…...

【ROS2】 默认的DDS通信中间件替换为Eclipse Cyclone_DDS (DDS配置方法)

ROS2替换中间件为Cyclone_DDS 1.一些介绍&#xff1a;&#xff09;2.不同DDS的RMW实现3.默认的FastDDS替换为Cyclone DDSi.安装依赖ii.编译 cyclone-dds 4.配置网络 1.一些介绍&#xff1a;&#xff09; 上一篇我们探讨了ros1和ros2编写launch的区别 【ROS2】launch启动文件编…...

迈向数智金融:机器学习金融科技新纪元的新风采

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

Linux安全加固:从攻防视角构建系统免疫

Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...