力扣287-寻找重复数
287. 寻找重复数 - 力扣LeetCode给定一个包含n 1个整数的数组nums其数字都在[1, n]范围内包括1和n可知至少存在一个重复的整数。假设nums只有一个重复的整数返回这个重复的数。你设计的解决方案必须不修改数组nums且只用常量级O(1)的额外空间。示例 1输入nums [1,3,4,2,2]输出2示例 2输入nums [3,1,3,4,2]输出3示例 3 :输入nums [3,3,3,3,3]输出3提示1 n 105nums.length n 11 nums[i] nnums中只有一个整数出现两次或多次其余整数均只出现一次进阶如何证明nums中至少存在一个重复的数字?你可以设计一个线性级时间复杂度O(n)的解决方案吗对 i0,1,2,…,n连一条从 i 到nums[i]的有向边得到一个有向图每个节点的入度都表示这个节点在 nums 中的出现次数以示例一的[1, 3, 4, 2, 2]为例因为2出现了两次下标分别为3和4所以一定会有 3 - 2 和 4 - 2 两条边2 的入度就是它出现的次数严谨地说假设nums[i] nums[j] k即 k 为那个重复出现的数那么就必然建立 i - k 和 j - k 两条边由于每个节点的出度都为1因为下标唯一所以 n 1 个节点有 n 1 条边这样的有向图必然有环找到环的入口即可注意可能有多个连通块例如[1, 2, 1, 4, 3]中3 和 4 是互相指向的两个节点构成一个连通块。因此要从节点 0 出发寻找那么问题就变成了找链表中环开始的节点使用 Floyd 判圈算法其实就是快慢指针假设头节点到入环口要走 a 步环长为 b相遇时慢指针走了 c 步那么快指针走了 2c 步设快指针比慢指针多走了 k 圈则有2c - c kb即 c kb慢指针从入环口开始在环中走了 c - a kb - a 步到达相遇点对于快指针从入环口开始在环中走了 2kb - a 步到达相遇点那么如果同时让快慢指针再走 a 步慢指针从入环口开始在环中走了 kb 步快指针则是 2kb 步而环长为 b所以此时慢指针从入环口开始走了 k 圈快指针 2k 圈刚好为整数意味着相遇点再走 a 步就是入环口也就是说相遇后我们可以让一个新指针从头节点出发让慢指针从相遇点出发二者相遇的点就是入环口。因为慢指针差 a 步到相遇点而 a 的含义就是头节点到入环口的步数class Solution { public int findDuplicate(int[] nums) { int slow 0, fast 0; // 0必定不在环上因为入度为0 while(true) { slow nums[slow]; // slow slow.next fast nums[nums[fast]]; // fast fast.next.next if(fast slow) { break; } } int head 0; while(slow ! head) { slow nums[slow]; head nums[head]; } return slow; } }

相关新闻

哪个品牌的智慧食堂系统好用

哪个品牌的智慧食堂系统好用

究竟哪家的智慧食堂系统更适合你?在信息化快速发展的今天,智慧食堂管理系统已经成为各大企业、高校等食堂管理的必备工具。各大品牌如云勤通、阿里云、腾讯云及一些其他行业内的企业,纷纷推出了智慧食堂管理系统。这些系统各有特点&#xff0…

2026/11/20 2:41:56 阅读更多 →
用飞算JavaAI搭建融汇智能支付与清结算平台:让交易安全、清晰、可追溯

用飞算JavaAI搭建融汇智能支付与清结算平台:让交易安全、清晰、可追溯

支付类项目最容易让人一上来就陷入“接口很多、状态很多、账也很多”的焦虑。一次支付背后,不只是创建订单和返回结果,还牵涉到渠道路由、退款、账户记账、清分、结算、对账以及异常补偿。真正难的地方,是让这些环节在同一条链路里看得清、追…

2026/11/12 23:35:35 阅读更多 →
DLAI 文档人工智能笔记(二)

DLAI 文档人工智能笔记(二)

Amazon S3是AWS提供的可扩展对象存储服务,适用于任何类型和大小的文件。可以把它想象成一个无限的数字文件柜,可以从互联网任何地方访问。无论你添加多少文件,它永远不会耗尽空间。这将作为你数据的中央存储库。 以下是S3的使用方式&#xf…

2026/11/19 13:23:16 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/19 21:38:27 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/19 21:38:49 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/19 21:39:09 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/19 21:36:50 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/19 21:37:45 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/19 21:36:20 阅读更多 →

日新闻

周新闻

月新闻