每日一题——O(1) 时间插入、删除和获取随机元素

简介: 每日一题——O(1) 时间插入、删除和获取随机元素

题目描述:

O(1) 时间插入、删除和获取随机元素:

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

// 测试
func main() {
  randomizedSet := Constructor()
  fmt.Println(randomizedSet.Remove(0))
  fmt.Println(randomizedSet.Remove(0))
  fmt.Println(randomizedSet.Insert(0))
  fmt.Println(randomizedSet.GetRandom())
  fmt.Println(randomizedSet.Remove(0))
  fmt.Println(randomizedSet.Insert(0))
}
type RandomizedSet struct {
  set []int
  // 元素:set中所在位置
  setMap map[int]int
}
func Constructor() RandomizedSet {
  return RandomizedSet{set: make([]int, 0), setMap: make(map[int]int)}
}
func (p *RandomizedSet) Insert(val int) bool {
  // map[k] 返回 val 和 ok
  if _, ok := p.setMap[val]; ok {
    return false
  }
  p.set = append(p.set, val)
  p.setMap[val] = len(p.set) - 1
  return true
}
func (p *RandomizedSet) Remove(val int) bool {
  if i, ok := p.setMap[val]; ok {
    // 将最后一个元素,放到i位置
    p.set[i] = p.set[len(p.set)-1]
    // 最后一个元素:现在的位置
    p.setMap[p.set[len(p.set)-1]] = i
    delete(p.setMap, val)
    // 丢弃最后一个元素
    p.set = p.set[0 : len(p.set)-1]
    return true
  }
  return false
}
func (p *RandomizedSet) GetRandom() int {
  // rand.Intn(n int) 
  // 返回一个取值范围在[0,n)的伪随机int值,如果n<=0会panic。
  return p.set[rand.Intn(len(p.set))]
}
相关文章
|
网络协议 Unix C语言
计算机里的套接字到底是什么
【4月更文挑战第3天】套接字在网络编程中扮演着重要角色,类似于电话和电话号码的概念。文章介绍了套接字的基本概念和工作原理,包括服务器端和客户端的初始化、连接建立、数据传输和断开连接的过程。
|
SQL 关系型数据库 MySQL
MySQL-主从架构的搭建
MySQL-主从架构的搭建
433 0
|
NoSQL 关系型数据库 MySQL
Redis持久化机制 RDB 和 AOF 的选择
Redis持久化机制 RDB 和 AOF 的选择
203 0
|
分布式计算 大数据 数据处理
Python入门与大数据处理环境配置指南
**Python入门与大数据处理环境配置** Python作为高级编程语言,因其简洁语法和丰富库资源,成为数据处理、AI和大数据分析首选。本文旨在介绍Python基础和环境配置,特别是针对大数据处理的环境搭建。首先,讲解Python语言基础,包括语言概述、基本语法(变量、数据类型、控制流语句、函数和模块)。接着,讨论如何安装Python环境,以及安装NumPy、Pandas等大数据处理库。对于大数据处理,可以选择本地环境或搭建分布式环境,如Hadoop和Spark,并提供相关API示例。最后,列出环境配置中可能遇到的问题及解决方案,如版本不兼容、库安装失败等,并提供参考资料以供深入学习。
358 3
|
存储 人工智能 缓存
AI 提示词模板相关的架构设计
现在很多企业纷纷研发大语言模型以解决业务问题。提示词在与模型交互中起到关键作用。为优化提示词模板的修改、提高渲染效率及确保安全性,架构设计注重可修改性、安全性、可靠性和性能。设计包括:将提示词存储在OSS以方便修改和版本控制;使用本地缓存提升读取性能;模板引擎增强灵活性;秘钥安全存储在加密系统中;并通过配置中心动态调整。此设计旨在提供高效、安全且可靠的AI交互体验等。
1042 78
AI 提示词模板相关的架构设计
|
存储 NoSQL Java
一天五道Java面试题----第十一天(分布式架构下,Session共享有什么方案--------->分布式事务解决方案)
这篇文章是关于Java面试中的分布式架构问题的笔记,包括分布式架构下的Session共享方案、RPC和RMI的理解、分布式ID生成方案、分布式锁解决方案以及分布式事务解决方案。
一天五道Java面试题----第十一天(分布式架构下,Session共享有什么方案--------->分布式事务解决方案)
|
Kubernetes Cloud Native 安全
探索云原生技术的优势和挑战
探索云原生技术的优势和挑战
733 0
探索云原生技术的优势和挑战
|
人工智能
解决方案评测|通义万相AI绘画创作获奖名单
通义万相AI绘画创作获奖名单正式发布!
354 1
|
JavaScript 前端开发 UED
小白请看! 大厂面试题 :如何用JS实现瀑布流
小白请看! 大厂面试题 :如何用JS实现瀑布流
|
缓存 自然语言处理 JavaScript
Web服务器的动态内容生成与处理
【8月更文第28天】在Web开发领域,动态内容生成是指根据用户请求实时生成页面内容的过程。这与静态内容生成不同,后者的内容在部署时就已经确定,不会随用户的请求而改变。动态内容生成通常依赖于服务器端脚本语言,例如PHP、Node.js等,它们能够根据不同的请求参数生成特定的响应数据。本文将探讨几种流行的服务器端脚本语言在动态网页生成中的作用及其优化方法,并提供相应的代码示例。
362 0

热门文章

最新文章