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

LeetCode 382. 链表随机节点

原题链接

难度:middle\color{orange}{middle}middle


题目描述

给你一个单链表,随机选择链表的一个节点,并返回相应的节点值。每个节点 被选中的概率一样

实现 SolutionSolutionSolution 类:

  • Solution(ListNodehead)Solution(ListNode head)Solution(ListNodehead) 使用整数数组初始化对象。
  • intgetRandom()int getRandom()intgetRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

示例:

输入
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
输出
[null, 1, 3, 2, 2, 3]解释
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
// getRandom() 方法应随机返回 1、2、3中的一个,每个元素被返回的概率相等。复制示例输入

提示:

  • 链表中的节点数在范围 [1,104][1, 10^{4}][1,104]
  • −104<=Node.val<=104-10^{4} <= Node.val <= 10^{4}104<=Node.val<=104
  • 至多调用 getRandomgetRandomgetRandom 方法 10410^{4}104

进阶:

  • 如果链表非常大且长度未知,该怎么处理?
  • 你能否在不使用额外空间的情况下解决此问题?

算法1

(记录所有链表元素)

我们可以在初始化时,用一个数组记录链表中的所有元素,这样随机选择链表的一个节点,就变成在数组中随机选择一个元素。

复杂度分析

  • 时间复杂度:初始化为 O(n)O(n)O(n),随机选择为 O(1)O(1)O(1),其中 nnn 是链表的元素个数。

  • 空间复杂度 : O(n)O(n)O(n),我们需要 O(n)O(n)O(n) 的空间存储链表中的所有元素。

C++ 代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:vector<int> arr;Solution(ListNode* head) {while (head) {arr.emplace_back(head->val);head = head->next;}}int getRandom() {return arr[rand() % arr.size()];}
};/*** Your Solution object will be instantiated and called as such:* Solution* obj = new Solution(head);* int param_1 = obj->getRandom();*/

算法2

(蓄水池抽样)

nnn 个元素,从中选 mmm 个,使得每个元素被选中的概率都是 m/nm/nm/n,该题中,m=1m = 1m=1

用一个变量 rrr 存储当前存储选择的数是多少。

  • 如果只有一个元素,则一定选择该数,r=xr = xr=x
  • 如果有两个数,换成当前数的概率为 1/21/21/2
  • 如果有三个数,换成当前数的概率为 1/31/31/3
  • 以此类推,这样,每个数被随机到的概率是一样的,且和 nnn 的大小无关。

复杂度分析

  • 时间复杂度:初始化为 O(1)O(1)O(1),随机选择为 O(n)O(n)O(n),其中 nnn 是链表的元素个数。

  • 空间复杂度 : O(1)O(1)O(1),我们只需要常数的空间保存若干变量。

C++ 代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* dummy;Solution(ListNode* head) {dummy = head;}int getRandom() {// c 代表获奖人数,n代表总人数int c = -1, n = 0;for (auto p = dummy; p; p = p->next) {n ++; // 人数加1if (rand() % n == 0) c = p->val;}return c;}
};/*** Your Solution object will be instantiated and called as such:* Solution* obj = new Solution(head);* int param_1 = obj->getRandom();*/

相关文章:

LeetCode 382. 链表随机节点

原题链接 难度&#xff1a;middle\color{orange}{middle}middle 题目描述 给你一个单链表&#xff0c;随机选择链表的一个节点&#xff0c;并返回相应的节点值。每个节点 被选中的概率一样 。 实现 SolutionSolutionSolution 类&#xff1a; Solution(ListNodehead)Solution…...

iOS开发AppleDeveloper中给别人授权开发者权限后,对方一直显示不了我的开发账号team

在iOS开发经常出现多人协作开发的情况。这时我们通常要发邮件邀请别的用户为开发者或者app管理就可以开发我们自己的项目了。但是这次我给别人授权开发者权限后&#xff0c;发现别人权限中没有证书相关权限如图&#xff1a;并且别人登录该账号后&#xff0c;在xcode中只有一个看…...

FreeRTOS数据类型和编程规范

目录 数据类型 变量名 函数名 宏的名 数据类型 每个移植的版本都含有自己的portmacro.h头文件&#xff0c;里面定义了2个数据类型 TickType_t FreeRTOS配置了一个周期性的时钟中断&#xff1a;Tick Interrupt每发生一次中断&#xff0c;中断次数累加&#xff0c;这被称为t…...

【python知识】win10下如何用python将网页转成pdf文件

一、说明 本篇记录一个自己享用的简单工具。在大量阅读网上文章中&#xff0c;常常遇到一个专题对应多篇文章&#xff0c;用浏览器的收藏根本不够。能否见到一篇文章具有搜藏价值&#xff0c;就转到线下&#xff0c;以备日后慢慢消化吸收。这里终于找到一个办法&#xff0c;将在…...

C语言常见关键字

写在前面 这个博客是结合C语言深度解剖这本书和我以前学的知识综合而成的,我希望可以更见详细的谈一下C语言的关键字,内容有点多,有错误还请斧正. 常见关键字 下面我们说下C语言的关键字,所谓的关键字是指具有特定功能的单词,我们可以使用关键字来帮助我们完成不同的事物.C语…...

【MT7628】固件开发-SDK4320添加MT7612E WiFi驱动操作说明

解压5G WiFi MT7612E驱动1.1解压指令 tar -xvf MT76x2E_MT7620_LinuxAP_V3.0.4.0_P2_DPA_20160308.tar.bz2 1.2解压之后会出现以下两个目录 rlt_wifi rlt_wifi_ap 1.3将解压后的文件拷贝到系统下 拷贝路径 RT288x_SDK/source/linux-2.6.36.x/drivers/net/wireless 内核中打开驱…...

如何从手工测试进阶自动化测试?阿里10年测开经验分享...

随着行业的竞争加剧&#xff0c;互联网产品迭代速度越来越快&#xff0c;QA 与测试工程师都需要在越来越短的测试周期内充分保证质量。可是&#xff0c;App 测试面临着很多挑战&#xff0c;比如多端发布、多版本发布、多机型发布等等&#xff0c;导致了手工测试很难完全胜任。因…...

C++复习笔记11

1. vector是表示可变大小数组的序列容器。 2. 就像数组一样&#xff0c;vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问&#xff0c;和数组一样高效。但是又不像数组&#xff0c;它的大小是可以动态改变的&#xff0c;而且它的大小会被…...

【MT7628】固件开发-SDK4320添加MT7628 WiFi驱动操作说明

解压2.4G WiFi MT7628驱动1.1解压指令 tar -xvf MT7628_LinuxAP_V4.1.0.0_DPA_20160310.tar.bz2 1.2解压之后会出现以下两个目录 mt_wifi mt_wifi_ap 1.3将解压后的文件拷贝到系统下 拷贝路径 RT288x_SDK/source/linux-2.6.36.x/drivers/net/wireless 内核中打开驱动编译修改R…...

C#开发的OpenRA游戏加载界面的实现

C#开发的OpenRA游戏加载界面的实现 游戏的UI是一个游戏必备, 但是游戏的UI都是自己处理的,不能使用像Windows自带的UI。 这样游戏的UI,其实也是使用游戏的方式来显示的, 只不过使用了低帧率的方式来显示。 比如OpenRA游戏界面,就会显示如下: 游戏的界面有很多,先从一个简…...

渲染农场优势是什么_云渲染农场怎么用?

在回答渲染农场的优势这个问题之前&#xff0c;我先申明一下本文中提到的渲染农场/云渲染平台/云渲染农场&#xff0c;都特指CG领域内的专业3D渲染平台&#xff0c;有一些文章会强调这个叫法的区别&#xff0c;但是业内一般都不会分这么细&#xff0c;所以也就不赘述了。渲染农…...

SoapUI、Jmeter、Postman三种接口测试工具的比较分析

目录 前言 1. 用例组织方式 2. 支持的接口类型与测试类型 3. 配置不同接口类型 4. 自定义变量以及变量的作用域 5. 数据源、生成器&#xff0c;进行参数化 6. 流程控制 7. 结果解析、展示 8. 断言 9. 脚本扩展能力 10. 团队协作 总结 重点&#xff1a;配…...

Python内置函数 — sort,sorted

1、sort 列表的属性方法&#xff0c;对列表进行排序&#xff0c;默认升序&#xff0c;返回None值。 源码注释&#xff1a; """ Sort the list in ascending order and return None.The sort is in-place (i.e. the list itself is modified) and stable (i.e.…...

mysql事务隔离级别

mysql锁机制及原理1.隔离级别2.实践2.1查看事务隔离级别2.2 设置隔离级别2.3 不可重复读2.4 幻读3.幻读怎么解决3.1 Record Lock3.2 Gap Lock3.3 Next-Key Lock引用&#xff1a;https://blog.csdn.net/xinyuan_java/article/details/1284932051.隔离级别 SERIALIZABLE(序列化)…...

【C++】string类(下)

文章目录1.迭代器(正向遍历)begin有两个版本2.反向迭代器(反向遍历)rbegin由两个版本3. at4. insert ——头插在pos位置前插入一个字符串在pos位置前插入n个字符在迭代器前插入一个字符5. erase从pos位置开始删除len个字符从迭代器位置开始删除6. replace——替换从pos位置开始…...

Elasticsearch: Prefix queries - 前缀查询

Prefix queries 被用于在查询时返回在提供的字段中包含特定前缀的文档。有时我们可能想使用前缀查询单词&#xff0c;例如 Leonardo 的 Leo 或 Marlon Brando、Mark Hamill 或 Martin Balsam 的 Mar。 Elasticsearch 提供了一个前缀查询&#xff0c;用于获取匹配单词开头部分&a…...

GEE学习笔记 七十七:GEE学习方法简介

这是一篇关于学习方法的思考探索&#xff0c;当然我不会大篇文章介绍什么学习方法&#xff08;因为我也不是这方面的专家?&#xff09;&#xff0c;这个只是总结一下我是如何学习GEE以及在学习中遇到问题时如何解决问题的。我写这篇文章的目的就是在和一些学习GEE的新同学接触…...

20基于主从博弈的智能小区代理商定价策略及电动汽车充电管理MATLAB程序

参考文档&#xff1a;《基于主从博弈的智能小区代理商定价策略及电动汽车充电管理》基本复现仿真平台&#xff1a;MATLABCPLEX/gurobi平台优势&#xff1a;代码具有一定的深度和创新性&#xff0c;注释清晰&#xff0c;非烂大街的代码&#xff0c;非常精品&#xff01;主要内容…...

长按power键,点击重启按钮,系统重启流程一

1.有可能会涉及到如下文件 2.文件流程...

数据的TCP分段和IP分片

本文简述下TCP分段和IP分片的区别与联系。 我们知道&#xff0c;用户空间的数据拷贝到内核空间的TCP发送缓冲区&#xff08;这个是一个结构体&#xff0c;叫sk_buffer&#xff0c;简称skb&#xff09;后就由内核网络协议栈做后续的封装和发送处理了&#xff0c;用户无需考虑下…...

HTML中嵌入B站视频

HTML中嵌入B站视频 在网页中实现一个HTML播放器需要先从b站获取视频嵌入代码, 以前嵌入代码可以从视频分享那里拿到, 现在好像不行了 必须是自己投稿的视频, 从投稿管理页面才能找到 复制嵌入代码 建一个.html文件, 放入下面代码 <!DOCTYPE html> <html><head…...

Mars3D Studio 的使用方法

Mars3D Studio的使用 1、介绍&#xff1a; mars3d Studio是mars3d研发团队于近期研发上线的一款 场景可视化编辑平台。拥有资源存档、团队协作、定制材质等丰富的功能。可以实现零代码构建一个可视化三维场景。 2、功能介绍 &#xff08;1&#xff09;数据上传&#xff1a…...

Flutter For Web实践

1 什么是Flutter Flutter是Google开源的一套UI工具包&#xff0c;帮助开发者通过一套代码库高效构建多平台精美应用&#xff0c;支持移动APP、web、桌面和嵌入式平台。Flutter和其他的跨平台解决方案的实现方式上有比较大的差异。 我们以React Native&#xff08;下文简称RN&…...

【神级Python代码】作为技术xiao白如何制作一款超炫酷的黑客主题代码雨?牛逼就完了。(源码分享学习)

前言 哈喽&#xff0c;我是木子&#xff0c;今天给大家制作一款超级炫酷的代码啦。 提到《黑K帝国》&#xff0c;字符雨可谓是让人印象深刻。 所有文章完整的素材源码都在&#x1f447;&#x1f447; 粉丝白嫖源码福利&#xff0c;请移步至CSDN社区或文末公众hao即可免费。 ​…...

供应链挑战迎刃而解!桑迪亚国家实验室使出“量子杀手锏”

桑迪亚国家实验室的科学家Alicia Magann&#xff08;右&#xff09;&#xff0c;Kenneth Rudinger&#xff08;左上&#xff09;&#xff0c;Mohan Sarovar&#xff08;左下&#xff09;和Matthew Grace&#xff08;未附图&#xff09;开发了基于反馈的量子优化算法&#xff08…...

java程序设计-ssm博客管理系统

博客管理系统是一个用于创建、管理和发布博客文章的应用程序。它通常包括一个后台管理界面&#xff0c;用于管理用户、文章、评论、标签等数据。同时&#xff0c;它还包括一个前端界面&#xff0c;用于展示博客文章并提供交互功能&#xff0c;例如评论和分享。 博客管理系统可…...

从0到1一步一步玩转openEuler--17 openEuler DNF(YUM)检查更新

文章目录17.1 检查更新17.2 升级17.3 更新所有的包和它们的依赖DNF是一款Linux软件包管理工具&#xff0c;用于管理RPM软件包。DNF可以查询软件包信息&#xff0c;从指定软件库获取软件包&#xff0c;自动处理依赖关系以安装或卸载软件包&#xff0c;以及更新系统到最新可用版本…...

SpringBoot-自动配置-@Import注解与@EnableAutoConfiguration注解

Import注解 Enable* 底层依赖于 Import 注解导入一些类&#xff0c;使用 Import 导入的类会被 Spring 加载到 IOC 容器中Import 提供了4种用法&#xff1a; 1.导入Bean2.导入配置类3.导入ImportSelector实现类&#xff1b;一般用于加载配置文件中的类4.导入ImportBeanDefinitio…...

【笔记】C#一维数组、多维数组和交错数组的区别总结

文章目录前言数组的概念1&#xff0c;一维数组&#xff1a;2&#xff0c;多维数组&#xff1a;3&#xff0c;交错数组&#xff1a;区别总结结语前言 &#x1f604;大家好&#xff0c;我是writer桑&#xff0c; 这是自己整理的 C# 数组笔记&#xff0c;方便自己学习的同时分享出…...

【SpringBoot】分布式日志跟踪—通过MDC实现全链路调用日志跟踪

一.MDC 1.MDC介绍 MDC&#xff08;Mapped Diagnostic Context&#xff0c;映射调试上下文&#xff09;是 log4j 和 logback 提供的一种方便在多线程场景下记录日志的功能。MDC 可以看成是一个与当前线程绑定的Map&#xff0c;可以往其中添加键值对。MDC 中包含的内容可以被同…...

wordpress如何调整文章位置/搜索引擎优化分析报告

Python不需要为变量指定数据类型 例如写出 abc 1&#xff0c;abc 就是整数类型&#xff0c;写 abc 1.0&#xff0c;变量 abc 就是浮点类型 Python 操作字符串&#xff0c;用单引号或双引号括起来 >>> "Hello World!" Hello World! 从键盘读取一个数字…...

上海建定建设工程信息网/网站seo系统

嵌入式安全元件&#xff08;eSE&#xff09;市场的企业竞争态势 该报告涉及的主要国际市场参与者有NXP Semiconductors (Netherlands)、Infineon (Germany)、STMicroelectronics (Switzerland)、Gemalto (Netherlands)、IDEMIA (France)、Beijing HuaDa ZhiBao Electronic Syst…...

品牌策划流程/昆明百度关键词优化

方法一&#xff1a;1、打开谷歌浏览器后&#xff0c;在任意标签页使用2、名字可以随意些&#xff0c;将网址输入&#xff1a;chrome://restart 点击保存按钮&#xff1b;3、在感觉Chrome 越来越卡的时候&#xff0c;点击下收藏栏中创建的 书签 &#xff0c;点击一下即可释放内…...

菏泽公司网站建设/天眼查询个人信息

声明&#xff1a; 本博客欢迎转发&#xff0c;但请保留原作者信息! 博客地址&#xff1a;http://blog.csdn.net/halcyonbaby 内容系本人学习、研究和总结。如有雷同&#xff0c;实属荣幸&#xff01;安装执行create-stack-user.sh脚本时&#xff0c;当前文件夹不要是devstack安…...

北京直销网站开发/磁力岛

在Unity手游开发中&#xff0c;经常用到插值运算&#xff0c;我们可以使用Mathf.Lerp自行去实现效果&#xff0c;但是使用插件提高了我们的开发效率&#xff0c;这里归结一下DoTween的基本使用方式以及效果说明&#xff1a; 直接代码&#xff1a; 1 using DG.Tweening;2 using …...

wordpress中国优化/自助建站网站

在页面展示图片中&#xff0c;总会遇到图片展示不符合自己想法的事情&#xff0c;比如固定了图片宽高&#xff0c;图片会变形 其实CSS提供了一个object-fit属性&#xff0c;object-fit: cover; 就可以解决图片变形的问题 介绍&#xff1a; object-fit 属性指定元素的内容应该如…...