专业网站网站设计,c 做的网站,长沙专业竞价优化公司,贵阳app开发公司哪家强文章目录题目描述思路 代码更新题目描述
可以理解成数组版本的 环形链表 II更多详细思路可见以上超链接。
思路 代码
如何转化成逻辑上的链表#xff1f;nums[i] 是 第 i 个结点的 next 指针构造成一个有 nums.length - 重复次数 个结点的链表如此#xff0…
文章目录题目描述思路 代码更新题目描述
可以理解成数组版本的 环形链表 II更多详细思路可见以上超链接。
思路 代码
如何转化成逻辑上的链表nums[i] 是 第 i 个结点的 next 指针构造成一个有 nums.length - 重复次数 个结点的链表如此该链表中肯定成环可以自己画数组转化成逻辑上的链表图理解下时间复杂度 O(n)空间复杂度 O(1)未修改数组重复证明slow 路程超过 nums.length / 2即可
class Solution {public int findDuplicate(int[] nums) {// 类似环形链表II用快慢指针做。看成一个环形链表, nums[i] 相当于 i.next// 链表中结点数 nums.length - 重复次数int slow nums[0], fast nums[0];// 第一次相遇结束do {slow nums[slow];fast nums[nums[fast]];} while(slow ! fast);// fast放到头重新开始run再次相遇就是答案fast nums[0];while(fast ! slow){fast nums[fast];slow nums[slow];}return fast;}
}更新
主要是不能修改原数组数字转换成节点重复数字相当于多个数字表示一个节点根据存储值对应下标来构造链表关系。
class Solution {public int findDuplicate(int[] nums) {int slow nums[0], fast nums[0];do {slow nums[slow];fast nums[nums[fast]];} while(slow ! fast);fast nums[0];while(slow ! fast) {fast nums[fast];slow nums[slow];}return slow;}
}
