首页 > 其他分享 >380. O(1) 时间插入、删除和获取随机元素.18071112

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

时间:2024-03-13 17:35:38浏览次数:26  
标签:RandomizedSet val insert int getRandom 380 插入 18071112 true

380. 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 。
 

提示:

-231 <= val <= 231 - 1
最多调用 insert、remove 和 getRandom 函数 2 * 105 次
在调用 getRandom 方法时,数据结构中 至少存在一个 元素。

使用哈希记录元素的索引,当删除元素时,将待删除元素与数组尾元素交换,然后减少数组长度以实现删除

class RandomizedSet {
public:
    vector<int>nums;
    map<int,int>book;

    RandomizedSet() {

    }
    
    bool insert(int val) {
        if(book[val])   return false;
        nums.push_back(val);
        //map中记录当前元素的索引
        book[val]=nums.size();
        return true;   
    }
    
    bool remove(int val) {
        if(!book[val])  return false;
        int n=nums.size();
        int exchange=nums[n-1];
        //将该元素移动到数组尾
        swap(nums[book[val]-1],nums[n-1]);
        book[exchange]=book[val];
        //数组长度减一
        nums.resize(n-1);
        book[val]=0;
        return true;
    }
    
    int getRandom() {
        int ram=rand()%nums.size();
        return nums[ram];
    }
};

/**
 * 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();
 */

标签:RandomizedSet,val,insert,int,getRandom,380,插入,18071112,true
From: https://www.cnblogs.com/SkyDusty/p/18071129

相关文章

  • 动态链表学习笔记:查找,插入与删除
    目录情境引入:一、数据的查找1.要求:2.思路:3.程序:4.运行:二、数据的插入 1.要求:2.思路: 3.程序: 4.运行:三、数据的删除1.要求:2.思路:3.程序:4.运行四、调整与小结:优化:运行情境引入:        学习了动态链表的输入输出后,若还需要对其进行进一步的操作,......
  • MySQL如果数据存在则更新,不存在则插入
    如果数据存在则更新,不存在则插入,MySQL有duplicate、replaceinto、replace三种方式如何更新数据?insertignoreinto又是如何插入数据的呢?准备表和基础数据测试MySQL版本:8.0.35usetestdb;#droptabletb_student;CREATETABLE`tb_student`(`id`intNOTNULLAUTO_IN......
  • lgP3807 lucas定理计算组合数
    有T次询问,每次给出整数n,m,p,计算C(n+m,n)%p的值。输入保证p为质数。1<=n,m,p<=1E5;1<=T<=10n较大,p较小且为质数时,可以用lucas定理来计算组合数:lucas(n,k,p)=lucas(n/p,k/p,p)*C(n%p,k%p,p)#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definer......
  • P3805 【模板】manacher
    https://www.luogu.com.cn/problem/P3805板子题比较模式的代码(书上整理):#include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<sstream>#include<string>#include<string.h>#include<iomanip>#in......
  • 基本操作之——Object插入
    insert_obj—Insertobjectsintoaniconicobjecttuple.  插入对象到图标对象数组中*以下实例展示了,在垂直两张图像中,插入一张蓝莓图像dev_update_off()dev_close_window()dev_open_window(0,0,640,480,'white',WindowHandle)set_display_font(WindowHandle,1......
  • 701. 二叉搜索树中的插入操作c
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/structTreeNode*insertIntoBST(structTreeNode*root,intval){if(!root){structTreeNode*......
  • 35. 搜索插入位置
    目录题目模板之二分搜索的左边界版题目给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。请必须使用时间复杂度为O(logn)的算法。示例1:输入:nums=[1,3,5,6],target=5输出:2示例2:输......
  • 自增长主键回显实现,批量数据插入
    1packagecom.atsyc.api.preparedstatement;23importorg.junit.Test;45importjava.sql.*;67publicclassPSOtherPart{8/*9*TODO:10*t_user插入一条数据,并且获取数据库自增长的主键11*使用总结:12*......
  • 147. 对链表进行插入排序(中)
    目录题目题解优化题目给定单个链表的头head,使用插入排序对链表进行排序,并返回排序后链表的头。插入排序算法的步骤:插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在......
  • 将Opencv的namedWindow( )函数创建的窗口插入显示在应用程序窗口客户区
    1、使用Opencv的namedWindow(WND_NAME,nFlag)//WND_NAME为窗口的名称 nFlag填入图模式有4种2、resizeWindow(wnd_name,宽,高)设置图片窗口的高、宽,3、根据窗口名hPicWnd= FindWindow(NULL,wnd_name)取得显示图片窗口的句柄  4、SetParent(hPicWnd ,应用......