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; } }
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; } }
