面试经典算法150题系列-O(1)时间插入、删除和获取随机元素

news/2024/9/25 12:44:48/

序言:这题可能相对之前的题稍微代码量大一些,但是别急,我们只有理清思路,其实实现起来也挺简单,重在理解,我在实现代码部分特地还增加了一些变量方法的详细解释,担心有人不懂ArrayList集合和哈希集合操作,在最后还进行了补充,篇幅较长,望君细细品读。

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 。

实现思路:

我们需要实现O(1)时间复杂度的时间插入、删除和获取随机元素
单独使用ArrayList集合或哈希集合,都没有办法实现,因为哈希集合不方便实现获取随机元素,ArrayList集合查询操作无法满足条件。这时不妨想想,哈希集合查询元素的时间复杂度为O(1),ArrayList集合删除最后一个元素,以及插入一个元素到最后都为O(1),且可以实现随机访问元素。
这样一想,我们是不是可以将二者进行结合呢?

因此我们先来进行对象初始化,需要定义3个对象:

(1)定义ArrayList集合对象:用于存储元素和删除元素

(2)定义哈希集合对象:用于查询元素

(3)定义随机数对象用于获取随机索引

然后进行方法的构思:

  • insert 方法首先检查值是否已经存在于HashMap中,如果存在,则返回false。如果不存在,将值添加到ArrayList的末尾,并在HashMap中记录这个值到其索引的映射。
  • remove 方法检查值是否存在于HashMap中,如果不存在,则返回false。如果存在,找到这个值的索引,将ArrayList的最后一个元素移动到要删除的元素的位置,并更新HashMap中的索引。然后,从ArrayList中删除最后一个元素,并从HashMap中删除对应的映射。
  • getRandom 方法使用Random对象生成一个随机索引,并从ArrayList中返回该索引处的元素。

实现代码:

java">import java.util.ArrayList; // 导入ArrayList类
import java.util.HashMap;   // 导入HashMap类
import java.util.Random;    // 导入Random类// 定义RandomizedSet类
class RandomizedSet {// 使用HashMap存储数字到索引的映射private HashMap<Integer, Integer> numToIndex;// 使用ArrayList存储集合中的所有数字private ArrayList<Integer> nums;// Random对象用于生成随机数private Random rand;// 构造函数,初始化HashMap、ArrayList和Random对象public RandomizedSet() {numToIndex = new HashMap<>();nums = new ArrayList<>();rand = new Random();}// 插入操作,如果元素已存在则返回false,否则插入并返回truepublic boolean insert(int val) {// 检查元素是否已存在if (numToIndex.containsKey(val)) {return false;}// 将元素添加到ArrayList的末尾,并记录其索引numToIndex.put(val, nums.size());nums.add(val);return true;}// 删除操作,如果元素不存在则返回false,否则删除并返回truepublic boolean remove(int val) {// 检查元素是否存在if (!numToIndex.containsKey(val)) {return false;}// 获取要删除元素的索引int removeIndex = numToIndex.get(val);// 获取ArrayList的最后一个元素int lastElement = nums.get(nums.size() - 1);// 将最后一个元素放到要删除的元素的位置nums.set(removeIndex, lastElement);// 更新最后一个元素在HashMap中的索引numToIndex.put(lastElement, removeIndex);// 从ArrayList中移除最后一个元素nums.remove(nums.size() - 1);// 从HashMap中移除要删除元素的映射numToIndex.remove(val);return true;}// 随机获取一个元素public int getRandom() {// 生成一个随机索引int randomIndex = rand.nextInt(nums.size());// 返回ArrayList中随机索引处的元素return nums.get(randomIndex);}
}
import java.util.ArrayList; // 导入ArrayList类
import java.util.HashMap;   // 导入HashMap类
import java.util.Random;    // 导入Random类// 定义RandomizedSet类
class RandomizedSet {// 使用HashMap存储数字到索引的映射private HashMap<Integer, Integer> numToIndex;// 使用ArrayList存储集合中的所有数字private ArrayList<Integer> nums;// Random对象用于生成随机数private Random rand;// 构造函数,初始化HashMap、ArrayList和Random对象public RandomizedSet() {numToIndex = new HashMap<>();nums = new ArrayList<>();rand = new Random();}// 插入操作,如果元素已存在则返回false,否则插入并返回truepublic boolean insert(int val) {// 检查元素是否已存在if (numToIndex.containsKey(val)) {return false;}// 将元素添加到ArrayList的末尾,并记录其索引numToIndex.put(val, nums.size());nums.add(val);return true;}// 删除操作,如果元素不存在则返回false,否则删除并返回truepublic boolean remove(int val) {// 检查元素是否存在if (!numToIndex.containsKey(val)) {return false;}// 获取要删除元素的索引int removeIndex = numToIndex.get(val);// 获取ArrayList的最后一个元素int lastElement = nums.get(nums.size() - 1);// 将最后一个元素放到要删除的元素的位置nums.set(removeIndex, lastElement);// 更新最后一个元素在HashMap中的索引numToIndex.put(lastElement, removeIndex);// 从ArrayList中移除最后一个元素nums.remove(nums.size() - 1);// 从HashMap中移除要删除元素的映射numToIndex.remove(val);return true;}// 随机获取一个元素public int getRandom() {// 生成一个随机索引int randomIndex = rand.nextInt(nums.size());// 返回ArrayList中随机索引处的元素return nums.get(randomIndex);}
}// 下面的代码是给测试用例看的,实际使用时不需要
/*** Your RandomizedSet object will be instantiated and called as such:* RandomizedSet obj = new RandomizedSet();* boolean param_1 = obj.insert(val);* boolean param_2 = obj.remove(val);* int param_3 = obj.getRandom();*/

下面是对每个部分的详细解释:

类成员变量

  • private HashMap<Integer, Integer> numToIndex;:一个哈希表,用于存储集合中每个数字到其在ArrayList中的索引的映射。这使得我们可以快速地访问和更新元素的位置。
  • private ArrayList<Integer> nums;:一个动态数组,用于存储集合中的所有元素。这允许我们快速地随机访问任何一个元素。
  • private Random rand;:一个随机数生成器,用于getRandom方法中生成随机索引。

构造函数

  • public RandomizedSet():构造函数初始化了HashMapArrayList,并创建了一个随机数生成器实例。

方法

  • public boolean insert(int val):向集合中插入一个新元素。

    • 首先检查该元素是否已经存在于HashMap中(即集合中是否已包含该值)。
    • 如果已存在,返回false表示插入失败。
    • 如果不存在,将元素添加到ArrayList的末尾,并在HashMap中记录这个新元素的值和它在ArrayList中的索引。
    • 返回true表示插入成功。
  • public boolean remove(int val):从集合中删除一个元素。

    • 首先检查该元素是否存在于HashMap中。
    • 如果不存在,返回false表示删除失败。
    • 如果存在,找到该元素在ArrayList中的索引,然后执行以下步骤:
      • ArrayList最后一个元素与要删除的元素交换位置。
      • 更新HashMap中最后一个元素的新索引。
      • ArrayList中删除最后一个元素。
      • HashMap中移除被删除元素的映射。
    • 返回true表示删除成功。
  • public int getRandom():随机返回集合中的一个元素。

    • 使用Random对象生成一个0到ArrayList长度减1的随机索引。
    • 返回ArrayList中该索引处的元素。

性能考虑

  • insertremove操作的平均时间复杂度是O(1),因为哈希表的插入、查找和删除操作都是O(1),而数组元素的交换和删除操作也是O(1)。
  • getRandom操作的时间复杂度是O(1),因为生成随机数和随机访问数组元素都是常数时间操作。

这种实现确保了RandomizedSet的所有操作都能以平均常数时间完成,同时支持随机访问元素。

知识补充:哈希集合和ArrayList集合(特点和操作)

·哈希集合和ArrayList集合的特点:

哈希集合(HashSet)
  1. 基于哈希表: HashSet 基于哈希表实现,通过哈希函数将元素分布到不同的桶(bucket)中。

  2. 元素唯一性: 只允许存储不重复的元素,即集合中的每个元素都是唯一的。

  3. 无序性: 元素在集合中没有特定的顺序,它们是无序的。

  4. 快速查找: 由于基于哈希表,HashSet 提供了快速的查找能力,平均时间复杂度为 O(1)。

  5. 动态扩容: 当元素数量增加到一定程度时,HashSet 会进行扩容以保持操作的效率。

  6. 常用操作: 提供了添加(add)、删除(remove)、检查存在性(contains)等操作。

  7. 内存占用: 通常比 ArrayList 占用更多的内存,因为需要存储额外的哈希表信息。

ArrayList
  1. 基于动态数组: ArrayList 是一个动态数组的实现,可以动态地增长和缩小。

  2. 元素有序: 元素在 ArrayList 中按照它们被插入的顺序排列,即元素是有序的。

  3. 快速随机访问: 允许快速随机访问任何位置的元素,时间复杂度为 O(1)。

  4. 插入和删除操作: 在列表末尾添加元素是 O(1) 的操作,但在中间或开始插入或删除元素可能需要 O(n) 的时间,因为可能需要移动其他元素。

  5. 容量调整: 当 ArrayList 的容量不足以容纳新元素时,会自动调整容量,这涉及到创建一个新的数组和复制旧元素。

  6. 常用操作: 提供了添加(add)、删除(remove)、获取元素(get)、设置元素(set)等操作。

  7. 内存连续性: ArrayList 的内存是连续的,这使得它在遍历和随机访问时非常高效。

总结
  • 哈希集合适合于需要快速查找和确保元素唯一性的场景。
  • ArrayList 适合于需要快速随机访问元素和保持元素插入顺序的场景。

选择使用哪种集合类型取决于具体的应用需求和性能考虑。理解每种集合的特点可以帮助开发者做出更合适的选择。

·哈希集合和ArrayList集合的操作

ArrayListHashMap是Java集合框架中的两个非常重要的类,分别提供了动态数组和哈希表的实现。下面是它们的基本操作:

ArrayList 基本操作
  1. 添加元素

    • add(E e): 向列表末尾添加一个元素。
    • add(int index, E element): 在指定位置插入一个元素。
  2. 获取元素

    • get(int index): 返回指定位置的元素。
  3. 设置元素

    • set(int index, E element): 用指定元素替换列表中指定位置的元素。
  4. 删除元素

    • remove(Object o): 移除列表中第一次出现的指定元素。
    • remove(int index): 删除指定位置的元素。
  5. 大小操作

    • size(): 返回列表中的元素数量。
  6. 遍历

    • 使用for-each循环或迭代器遍历列表中的元素。
  7. 清空列表

    • clear(): 移除列表中的所有元素。
HashMap 基本操作
  1. 添加键值对

    • put(K key, V value): 将指定的值与此映射中的指定键关联。
  2. 获取值

    • get(Object key): 返回指定键所映射的值。
  3. 删除键值对

    • remove(Object key): 如果存在一个键的映射关系,则将其从映射中移除。
  4. 检查存在性

    • containsKey(Object key): 如果映射包含键的映射关系,则返回true。
  5. 键集操作

    • keySet(): 返回映射中包含的键的Set视图。
  6. 值集操作

    • values(): 返回映射中包含的值的Collection视图。
  7. 条目集操作

    • entrySet(): 返回映射中包含的键值映射关系的Set视图。
  8. 大小操作

    • size(): 返回映射中键值对的数量。
  9. 清空映射

    • clear(): 移除映射中的所有键值对。
  10. 遍历

    • 使用for-each循环或迭代器遍历键、值或键值对。
示例代码

以下是一些使用ArrayListHashMap的示例代码:

java">import java.util.ArrayList;
import java.util.HashMap;public class Example {public static void main(String[] args) {// ArrayList示例ArrayList<String> list = new ArrayList<>();list.add("Apple"); // 添加元素System.out.println(list.get(0)); // 获取元素list.set(0, "Banana"); // 设置元素list.remove("Apple"); // 删除元素System.out.println(list.size()); // 获取大小list.clear(); // 清空列表// HashMap示例HashMap<Integer, String> map = new HashMap<>();map.put(1, "Apple"); // 添加键值对String value = map.get(1); // 获取值map.remove(1); // 删除键值对boolean contains = map.containsKey(1); // 检查键是否存在System.out.println(map.size()); // 获取大小map.clear(); // 清空映射}
}

这些基本操作为使用ArrayListHashMap提供了强大的灵活性,使得它们成为处理集合数据时的首选工具。


http://www.ppmy.cn/news/1505929.html

相关文章

OpenNebula-6.9.80中文详细部署安装

目录 OpenNebula介绍 主要特点 应用场景 一. 虚拟机准备 二. 下载安装 1. 导入yum源 2. 数据库配置 3. 安装包 4. 设置配置 数据存放位置 端口介绍 命令介绍 OpenNebula介绍 OpenNebula 是一个开源的云计算平台&#xff0c;主要用于创建和管理虚拟化环境。它被设…

【Redis】Redis 数据类型

文章目录 前言1 通用知识1.1 基本全局命令1.2 数据结构和内部编码 2 String2.1 类型介绍2.2 相关命令2.2.1 SET/GET 系列命令2.2.2 INCR/DECR 计数系列命令2.2.3 其他命令2.2.4 命令小结 2.3 内部编码2.4 应用场景2.4.1 缓存功能2.4.2 计数功能2.4.3 共享会话2.4.4 验证码功能 …

【运维项目经历|039】Ceph高性能云存储集群部署与优化

🍁博主简介: 🏅云计算领域优质创作者 🏅2022年CSDN新星计划python赛道第一名 🏅2022年CSDN原力计划优质作者 🏅阿里云ACE认证高级工程师 🏅阿里云开发者社区专家博主 💊交流社区:CSDN云计算交流社区欢迎您的加入! 目录 项目名称 项目背景 项目目标 项目成果…

gin框架 自定义404错误页面,自定义500等服务端异常,业务异常,根据不同异常类型显示不同的异常页面方法 整理

在gin框架中&#xff0c;要显示自定义的异常页面&#xff0c;首先需要通过gin路由对象中的LoadHTMLFiles或者LoadHTMLGlob方法加载自定义的错误页面模板文件&#xff0c; 然后定义符合 gin.HandlerFunc 类型的路由处理函数/方法 &#xff0c;即只有一个参数(c *ginx.XContext)的…

英特尔凌动® P5300 和 P5700 处理器使企业能够优化现代网络基础架构、安全加速器和存储设备之间的性能和成本平衡。

介绍英特尔凌动 P5300 和 P5700 处理器 英特尔凌动处理器提供核心数和硬件功能各异的多种配置&#xff0c;用于支持不同的边缘用例。基于 10 纳米工艺的先进微架构与一组强大的加速器相结合&#xff0c;带来卓越的每核性能和先进的数据包处理能力。这些平台基于高能效的系统级…

TCL 实业 x TiDB丨从分销转向零售,如何考虑中台建设和数据库选型?

导读 在数字化转型的浪潮中&#xff0c;TCL 实业通过“新方舟”项目构建统一中台&#xff0c;实现了从分销向零售的转型&#xff0c;显著提升了业务精准度和效率。本文根据 InfoQ 记者高玉娴对 TCL 实业企业架构部架构师蔡玖发的采访整理&#xff0c;揭秘了 TCL 实业在这一转型…

【iOS】AutoreleasePool自动释放池的实现原理

目录 ARC与MRC项目中的main函数自动释放池autoreleasepool {}实现原理AutoreleasePoolPage总结 objc_autoreleasePoolPush的源码分析autoreleaseNewPageautoreleaseFullPageautoreleaseNoPage autoreleaseFast总结 autorelease方法源码分析objc_autoreleasePoolPop的源码分析po…

计算数学精解【3】-C++计算基础(3)

文章目录 运算,- 加减法* / 乘除法逐元 乘法逐元 除法逐元综合运算矩阵乘法与加减法 转置、共轭、伴随矩阵点乘法,叉积 大整数GMP概述GMP安装 [cygwin](https://cygwin.com/install.html)安装 gmpexample Eigen基本属性和运算 读写文件概述example csv读文件读取每个字段读取机…