​LeetCode刷题实战380:O(1) 时间插入、删除和获取随机元素

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 O(1) 时间插入、删除和获取随机元素,我们先来看题面:
https://leetcode-cn.com/problems/insert-delete-getrandom-o1/
设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。
insert(val):当元素 val 不存在时,向集合中插入该项。
remove(val):元素 val 存在时,从集合中移除该项。
getRandom:随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例


// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ,表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);

// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();

// 从集合中移除 1 ,返回 true 。集合现在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中,所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的数字,getRandom 总是返回 2 。
randomSet.getRandom();

解题

利用动态数组的下标索引实现常数时间内的插入和随机元素的访问,
再利用哈希表实现常数时间的删除操作:将删除元素和最后一个元素交换,将最后一个元素删除

class RandomizedSet {
private:
 unordered_map<int,int> hash;//哈希实现删除
 vector<int> v;//动态数组实现插入和随机访问
public:
 /** Initialize your data structure here. */
 RandomizedSet() {

}
 
 /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
 //当元素 val 不存在时,向集合中插入该项。
 bool insert(int val) {
  if(hash.find(val) != hash.end()) return false; //如果集合中已经存在val,返回false,
  v.push_back(val);//否则插入到数组末尾
  hash[val] = v.size() - 1;//
  return true;
 }
 
 /** Removes a value from the set. Returns true if the set contained the specified element. */
 //元素 val 存在时,从集合中移除该项。
 bool remove(int val) {
  if(hash.find(val) == hash.end()) return false;//如果集合中不存在val,返回false
  int lastPos = v.size() - 1;//数组最后一个元素位置
  int valPos = hash[val];//将被删除值和数组最后一位进行交换
  v[valPos] = v[lastPos];
  v.pop_back();//删除
  hash[v[valPos]] = valPos;//被交换的值下标发生变化,需要更新
  hash.erase(val); //哈希表中删除val的项
  return true;
 }
 
 /** Get a random element from the set. */
 //随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
 int getRandom() {
 int size = v.size();
 int pos = rand() % size;//对下标产生随机数
 return v[pos];//数组可以根据下表返回
 }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。
上期推文:

LeetCode1-360题汇总,希望对你有点帮助!

LeetCode刷题实战361:轰炸敌人

LeetCode刷题实战362:敲击计数器

LeetCode刷题实战363:矩形区域不超过 K 的最大数值和
LeetCode刷题实战364:加权嵌套序列和 II
LeetCode刷题实战365:水壶问题
LeetCode刷题实战366:寻找二叉树的叶子节点
LeetCode刷题实战367:有效的完全平方数
LeetCode刷题实战368:最大整除子集数
LeetCode刷题实战369:给单链表加一
LeetCode刷题实战370:区间加法
LeetCode刷题实战371:两整数之和
LeetCode刷题实战372:超级次方
LeetCode刷题实战373:查找和最小的K对数字
LeetCode刷题实战374:猜数字大小
LeetCode刷题实战375:猜数字大小 II
LeetCode刷题实战376:摆动序列
LeetCode刷题实战377:组合总和 Ⅳ
LeetCode刷题实战378:有序矩阵中第 K 小的元素
LeetCode刷题实战379:电话目录管理系统
(0)

相关推荐

  • 第八章 散列表

    自我测试 本篇文章的测试用例及调试方法见前言 说明 散列算法的作用是尽可能快地在数据结构中找到一个值.在之前的章节中,你已经知道如果要在数据结构中获得一个值(使用get方法),需要遍历整个数据结构来找 ...

  • LeetCode 1128. 等价多米诺骨牌对的数量(简单)

    1128. 等价多米诺骨牌对的数量 给你一个由一些多米诺骨牌组成的列表 dominoes. 如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌,我们就认为这两张牌是等价的. ...

  • WTF Python: 开启你的懵逼模式

    What the f*ck Python? Python很流行很易学,但有时,Python代码片段的结果可能让小白们直接懵逼,现在大邓跟你一起开启懵逼模式 wtf-1 开胃菜hash some_dic ...

  • 3W 字详解 Java 集合

    开源前哨 93篇原创内容 公众号 数据结构作为每一个开发者不可回避的问题,而 Java 对于不同的数据结构提供了非常成熟的实现,这一个又一个实现既是面试中的难点,也是工作中必不可少的工具,在此,笔者经 ...

  • ​LeetCode刷题实战215:数组中的第K个最大元素

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战378:有序矩阵中第 K 小的元素

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战260:只出现一次的数字 III

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战258:各位相加

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战257:二叉树的所有路径

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战256:粉刷房子

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战262:行程和用户

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战255:验证前序遍历序列二叉搜索树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战263:丑数

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...