力扣题287寻找重复数
发布日期:2022-03-04 11:48:15
浏览次数:4
分类:技术文章
本文共 1117 字,大约阅读时间需要 3 分钟。
给定一个包含 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 = [1,1]
输出:1 示例 4:输入:nums = [1,1,2]
输出:1提示:
1 <= n <= 105
nums.length == n + 1 1 <= nums[i] <= n nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次进阶:
如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?1.使用双重循环暴力法,会超出时间限制,并且这道题不允许修改数组,也不能先排序。还有一个条件就是不是1~n的数字都会出现一遍,重复的整数会出现两次或多次,如果1~n的整数都必须出现一遍,那就直接对整个数组求和再减去1~n的和就是那个重复的整数了。
2.题解:Floyd 判圈算法(龟兔赛跑算法)。
参考:
对nums数组建图,每个位置i连一条i→nums[i]的边。比如对于nums = [1,3,4,2,2]这个例子,
下标与元素值关系如下:
元素值 | 1 | 3 | 4 | 2 | 2 |
下标 | 0 | 1 | 2 | 3 | 4 |
可以形成如下的环:
class Solution { public int findDuplicate(int[] nums) { int slow = 0;//慢指针 int fast = 0;//快指针 do { slow = nums[slow];//慢指针一次走一步 fast = nums[nums[fast]];//快指针一次走两步 } while (slow != fast);//说明存在环,并且在环中相遇了 slow = 0;//相遇后将slow从头开始,此时快慢指针都走一步,再次相遇的地方就是环的入口,即重复的数字 while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; }}
题源:
转载地址:https://blog.csdn.net/xxyneymar/article/details/121920037 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月21日 09时51分03秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
beep
2019-05-08
远程控制
2019-05-08
vs2008快捷键极其技巧
2019-05-08
total commande
2019-05-08
oracle
2019-05-08
最近项目问题
2019-05-08
杀死 进程并 重启(关机用 -s)
2019-05-08
oracle 不同数据库表复制新建
2019-05-08
oracle 服务器配置
2019-05-08
inno setup --regedit
2019-05-08
!!!
2019-05-08
sql 小东西
2019-05-08
mysql
2019-05-08
删除 .svn 文件夹
2019-05-08
ssh 乱码
2019-05-08
安装驱动及其 shell基础命令
2019-05-08
SourceInsight and Atyle 转帖
2019-05-08
mysql 存储过程
2019-05-08
zhuan linux dll
2019-05-08
makefile 的一些小东西
2019-05-08