市桥做网站的公司,牡丹区建设局网站,购门户网站系统,国外客户推广网站题目
给定一个包含 n 1 个整数的数组 nums #xff0c;其数字都在 [1, n] 范围内#xff08;包括 1 和 n#xff09;#xff0c;可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 #xff0c;返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums…题目
给定一个包含 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提示
1 n 105nums.length n 11 nums[i] nnums 中 只有一个整数 出现 两次或多次 其余整数均只出现 一次 解答
源代码
class Solution {public int findDuplicate(int[] nums) {int slow 0, fast 0;slow nums[slow];fast nums[nums[fast]];while (slow ! fast) {slow nums[slow];fast nums[nums[fast]];}slow 0;while (slow ! fast) {slow nums[slow];fast nums[fast];}return slow;}
}
总结
把数组看作链表好巧妙的思路看作链表后就用环形链表的思路解题参考 [142.环形链表Ⅱ] 的题解寻找环形链表的入口的下标即为重复数因为有两个节点的下一个节点都是这个节点。
