从事网站建设,淘宝如何做推广,wordpress 禁用所有插件,校园宿舍网网络设计案例287.寻找重复数 方法#xff1a;使用快慢指针
使用环形链表II的方法解题#xff08;142.环形链表II#xff09;#xff0c;使用 142 题的思想来解决此题的关键是要理解如何将输入的数组看作为链表。 首先明确前提#xff0c;整数的数组 nums 中的数字范围是 [1,n]。考虑一…287.寻找重复数 方法使用快慢指针
使用环形链表II的方法解题142.环形链表II使用 142 题的思想来解决此题的关键是要理解如何将输入的数组看作为链表。 首先明确前提整数的数组 nums 中的数字范围是 [1,n]。考虑一下两种情况
如果数组中没有重复的数以数组 [1,3,4,2]为例我们将数组下标 n 和数 nums[n] 建立一个映射关系 f(n) 其映射关系 n-f(n)为 0-1 1-3 2-4 3-2 我们从下标为 0 出发根据 f(n)计算出一个值以这个值为新的下标再用这个函数计算以此类推直到下标超界。这样可以产生一个类似链表一样的序列。 0-1-3-2-4-null如果数组中有重复的数以数组 [1,3,4,2,2] 为例,我们将数组下标 n 和数 nums[n] 建立一个映射关系 f(n) 其映射关系 n-f(n) 为 0-1 1-3 2-4 3-2 4-2 同样的我们从下标为 0 出发根据 f(n)f(n)f(n) 计算出一个值以这个值为新的下标再用这个函数计算以此类推产生一个类似链表一样的序列。 0-1-3-2-4-2-4-2-…… 这里 2-4 是一个循环那么这个链表可以抽象为下图 从理论上讲数组中如果有重复的数那么就会产生多对一的映射这样形成的链表就一定会有环路了
综上 1.数组中有一个重复的整数 – 链表中存在环 2.找到数组中的重复整数 – 找到链表的环入口
至此问题转换为 142 题。那么针对此题快、慢指针该如何走呢。根据上述数组转链表的映射关系可推出 142 题中慢指针走一步 slow slow.next 本题 slow nums[slow] 142 题中快指针走两步 fast fast.next.next 本题 fast nums[nums[fast]]
class Solution {/*** 287.数组nums有n1个整数,均位于[1,n]内,可知至少存在一个重复整数;假设nums中只有一个重复整数,找出该整数* 要求:不能修改nums且空间复杂度为O(1)* 方法:根据nums构造链表,链表中每个节点既表示nums中下标,又表示nums中值* 如[1,3,4,2]对应链表0-1-3-2-4* nums对应的链表中,每个节点的出度都为1,因为nums.length n1,所以nums[n]是存在的,* 进而链表中第n个节点(尾结点)又会指向一个前驱节点,必定形成环* 对于[1,3,4,2,2],链表尾的4号节点又会指向2号节点,形成环,2号节点是环的入口,* 其入度又为2,代表着nums中出现了两次2这个取值,因此2就是重复整数* 现在,问题就转化成了142题的环形链表入口检测问题* */public int findDuplicate(int[] nums) {int n nums.length - 1;int slow 0, fast 0;slow nums[slow]; // 对于本题, slow slow.next对应于slow nums[slow]fast nums[nums[fast]]; // fast fast.next.next对应于fast nums[nums[fast]]// 第一阶段slow与fast相遇判断成环while (slow ! fast) {slow nums[slow];fast nums[nums[fast]];}// 第二阶段:找到入环点// slow与fast相遇时,假设slow走过的路程是lb,其中l是slow入环前走过的路程,b是slow入环后走过的路程// 假设环的长度为r,则fast走过的路程可以表达为2(lb)lbk*r,整理后可得lk*r-b// 上述等式意味着,若一个指针p1从链表头开始前进,当他到达环的入口时(走过l的路程),// 另一个从slow与fast相遇的位置出发的指针p2也回到了环的入口(走过lk*r-b的路程),此时二者第一次相遇// 因此设置这样两个指针,当p1与p2第一次相遇,即找到了环的入口int p1 0, p2 slow;while (p1 ! p2) {p1 nums[p1];p2 nums[p2];}return p1;}
}
