重庆网站建设优斗士,网站收录很好没排名,怎样建设与维护自己的平台网站,维护一个网站要多少钱287. 寻找重复数 - 力扣#xff08;LeetCode#xff09;
题目描述 给定一个包含 n 1 个整数的数组 nums #xff0c;其数字都在 [1, n] 范围内#xff08;包括 1 和 n#xff09;#xff0c;可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 #xff0c;返…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
题目思路 这道题在LeetCode中是一道难度为中的题型原因就是题目限制了不修改原数组并且只能用常量级的空间。 假设没有限制那一般的思路可以是以下几种 ①利用map容器key就是nums中的数value从0开始递增如果value等于2时直接返回当前的nums[i]用一次循环即可使用的空间为O(n) ②利用sort函数对nums进行排序由于数字都在[1, n]中并且只存在一个重复数字用一次循环遍历当nums[i - 1] nums[i]时返回即可但是修改了原数组 下面考虑题目限制LeetCode官方提供了三种方法其中一种方法利用的二进制具体的可看官方题解下面利用Floyd判圈算法解决这个题目。
对于Floyd算法原理可参照我的上一篇博客Floyd判圈算法——环形链表C-CSDN博客
为了方便理解以数组[1, 2, 3, 4, 5, 6, 4]为例
怎么把这个数组抽象成龟兔赛跑问题呢
抽象跑道 从数组的第一个位置开始nums[0]即为跑道的起点由于nums[0] 1 那下一个点就是索引为1的点nums[1]由于nums[1] 2 那下一个点就是nums[2]以此类推……绘图如下 可以看到我们所求的重复数就是环的入口点。 过程推演 最开始乌龟和兔子都在起始点1的位置兔子的速度是乌龟的两倍即乌龟向前走一步兔子就向前走两步。 第一步寻找相遇点 ①乌龟从1→2兔子从1→3 ②乌龟从2→3兔子从3→5 ③乌龟从3→4兔子从5→4在此刻乌龟与兔子相遇 Notes此时并没有结束并不是所有的相遇点对应的值都是环的入口点如果环上还有一个数字相遇点就会发生改变。 第二步寻找环的入口点 将乌龟置为起点1处将兔子置为相遇点4处同步两者的速度为1 ①乌龟从1→2兔子从4→5 ②乌龟从2→3兔子从5→6 ③乌龟从3→4兔子从6→4在此刻乌龟与兔子相遇这个时候对应的值才是正确的值只是这个例子相遇点恰好在环的入口点上。
代码实现
class Solution {
public:int findDuplicate(vectorint nums) {//利用Floyd判圈算法int slow 0;int fast 0;do{slow nums[slow];fast nums[nums[fast]];}while(slow ! fast);slow 0;while(slow ! fast){slow nums[slow];fast nums[fast];}return slow;}
};
结果展示
