【技巧】LC 287.寻找重复数

文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接287.寻找重复数2、题目描述二、个人思路整理1、思路分析核心思路快慢指针Floyd判圈算法将数组抽象成一个带环链表每个下标i ii看作一个节点节点指向的下一个节点是nums [ i ] \text{nums}[i]nums[i]。因为数值范围在[ 1 , n ] [1, n][1,n]而下标范围是[ 0 , n ] [0, n][0,n]所以从下标 0 出发不会成环到 0 本身没有元素的值为 0 指向下标 0。由于存在重复数字target \text{target}target会有至少两个不同的下标指向同一个节点target \text{target}target入度≥ 2 \ge 2≥2这必然导致图里存在环且环的入口就是这个重复的数字。问题完全转化为 142.环形链表 II快指针走两步fast nums[nums[fast]]慢指针走一步slow nums[slow]直到两者在环内相遇。让慢指针回到起点 0快慢指针每次都走一步再次相遇的位置即为环的入口重复数。2、解题代码classSolution{public:intfindDuplicate(vectorintnums){// 将数组看作链表i - nums[i]// 初始时快指针走两步慢指针走一步以避开 nums[0] nums[0] 的初始相同状态intslownums[0];intfastnums[nums[0]];// 阶段一Floyd 判圈寻找快慢指针在环内的相遇点while(slow!fast){slownums[slow];// 慢指针每次前进一步fastnums[nums[fast]];// 快指针每次前进两步}// 阶段二寻找环的入口即重复的数字// 设起点到环入口距离为 a相遇点顺着环走到达入口的距离也为 a// 将慢指针重置到起点 0快慢指针同步每次前进一步slow0;while(slow!fast){slownums[slow];fastnums[fast];}// 再次相遇的点即为环的入口也就是出现入度 2 的重复数值returnslow;}};复杂度分析时间复杂度为O ( n ) O(n)O(n)因为快慢指针在环内至多走常数圈即可相遇并找到入口。空间复杂度为O ( 1 ) O(1)O(1)仅使用了两个指针变量在原数组上做链式跳转。三、知识风暴快慢指针Floyd 判圈算法是本题的核心概念。它本质上是把数组抽象成一张「隐式链表」图每个下标i ii是一个节点节点指向的下一个节点是nums [ i ] \text{nums}[i]nums[i]。由于数值范围在[ 1 , n ] [1, n][1,n]而下标范围是[ 0 , n ] [0, n][0,n]从下标 0 出发必然进入一个环而环的入口正是那个重复的数字。算法核心思想环的必然性因为存在重复数字target \text{target}target至少有两个不同的下标指向同一个节点target \text{target}target入度≥ 2 \ge 2≥2这必然导致图中存在环且环的入口就是这个重复的数字。两阶段相遇第一阶段让快指针每次走两步、慢指针每次走一步两者必在环内相遇第二阶段把慢指针重置回起点 0快慢指针同步每次走一步再次相遇的位置即为环的入口。与哈希法的区别哈希法用额外空间记录访问过的下标O ( n ) O(n)O(n)空间而 Floyd 判圈只用两个指针变量空间复杂度降到O ( 1 ) O(1)O(1)且不修改原数组。常见对比快慢指针 vs 哈希集合快慢指针空间O ( 1 ) O(1)O(1)时间O ( n ) O(n)O(n)不修改原数组适合「只读」场景但需要理解环的数学性质。哈希集合实现直观每访问一个下标就存入集合遇到重复即答案但空间O ( n ) O(n)O(n)在数据量大时更耗内存。共同点两者都依赖「从下标 0 出发必然进入环」这一结构特性区别在于是否用额外空间记录访问历史。双指针与原地算法的设计思想核心思想快慢指针在环内至多走常数圈即可相遇无需遍历整个数组因此时间复杂度为O ( n ) O(n)O(n)。与本题的联系本题的「数组即链表」映射把「找重复数」转化为「找环入口」与 142.环形链表 II 完全同构。注意事项初始时快指针必须走两步fast nums[nums[0]]慢指针走一步slow nums[0]以避开nums[0] nums[0]的初始相同状态。使用要点边界处理数值范围在[ 1 , n ] [1, n][1,n]下标范围在[ 0 , n ] [0, n][0,n]因此从下标 0 出发不会成环到 0 本身没有元素的值为 0 指向下标 0。指针跳转慢指针slow nums[slow]走一步快指针fast nums[nums[fast]]走两步注意快指针是「两次取值」而非「一次取值再自增」。入口证明设起点到环入口距离为a aa相遇点顺着环走到入口的距离也为a aa因此第二阶段把慢指针重置到起点后两者同步前进必在入口相遇。结果返回第二阶段再次相遇的点即为环的入口也就是出现入度≥ 2 \ge 2≥2的重复数值直接返回即可。算法变体与扩展环形链表 IILeetCode 142链表版找环入口与本题的「数组即链表」映射完全同构思路一致。环形链表LeetCode 141只判断是否存在环不要求找入口是 Floyd 判圈的最简版本。缺失的第一个正数LeetCode 41同样利用「数组下标与数值的映射」做原地标记与本题共享「用数组本身当哈希表」的思想。数组中重复的数据LeetCode 442用「数值取负」标记访问过的元素与本题的「入度≥ 2 \ge 2≥2」判定异曲同工。相关 LeetCode 例题141. 环形链表判断是否存在环142. 环形链表 II找环入口与本题同构41. 缺失的第一个正数数组下标与数值映射442. 数组中重复的数据原地标记重复元素