网站每年维护费用,天津智能网站建设,手机网站建站系统,做网站运营需要做哪些给定一个包含 n 1 个整数的数组 nums#xff0c;其数字都在 1 到 n 之间#xff08;包括 1 和 n#xff09;#xff0c;可知至少存在一个重复的整数。假设只有一个重复的整数#xff0c;找出这个重复的数。
示例 1:
输入: [1,3,4,2,2] 输出: 2 示例 2:
输入: [3,1,3,4…给定一个包含 n 1 个整数的数组 nums其数字都在 1 到 n 之间包括 1 和 n可知至少存在一个重复的整数。假设只有一个重复的整数找出这个重复的数。
示例 1:
输入: [1,3,4,2,2] 输出: 2 示例 2:
输入: [3,1,3,4,2] 输出: 3 说明
不能更改原数组假设数组是只读的。 只能使用额外的 O(1) 的空间。 时间复杂度小于 O(n2) 。 数组中只有一个重复的数字但它可能不止重复出现一次。 思路
通过数组构建一个循环链表之后通过快慢指针找出循环链表环的入口就是重复的数
例如题中给出的[1,3,4,2,2]i指向的是nums[i]
所以可以构建循环链表
1--3
1--3--2
1--3--2--4
1--3--2--4--2
可以看出构建出了一个循环链表
因为快指针走两步慢指针走一步每次快比慢多走一步所以如果有环最后一定可以相遇 相遇之后
我们设定环入口前的长度为a从环的入口继续走 b 步到达相遇位置从相遇位置继续走 c步回到环的入口
所以环长Rbc
慢指针走了ab步
所以快指针走了2*(ab)步
因为在相遇时快比慢是多走了n圈环
所以也可以说快指针走了abn*L步
所以2*(ab) abn*L
所以abn*L
所以现在让某一个指针从头开始走另一个从环入口开始走每次都是走一步
因为ab的距离是环长度的n倍所以他们一定会在环的 入口相遇。
我们就可以求出这个环的入口。
代码
//1--3--2--4--2class Solution {public int findDuplicate(int[] nums) {int fast 0, slow 0;while(true) {fast nums[nums[fast]];slow nums[slow];if(slow fast) {fast 0;while(nums[slow] ! nums[fast]) {fast nums[fast];slow nums[slow];}return nums[slow];}}}}
