一、题目描述给定一个包含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二、解题思路总览方法时间复杂度空间复杂度说明Floyd 判圈快慢指针O(n)O(1)转化为环形链表检测二分查找O(n log n)O(1)基于抽屉原理位运算O(n)O(1)统计每一位出现次数哈希表O(n)O(n)简单但不符合要求Floyd 判圈是满足 O(1) 空间的最优解。三、方法一Floyd 判圈算法推荐3.1 核心思想将数组转化为环形链表数组值代表下一个节点的索引因为有重复数字所以存在环找到环的入口点就是重复数字为什么能转化成环形链表数组: [1, 3, 4, 2, 2] 索引: 0 - 1 - 3 - 2 - 4 - 2 - 3 - 2 - 4 - ... 值: 1 3 4 2 2 从索引0出发: 0 - nums[0] 1 1 - nums[1] 3 3 - nums[3] 2 2 - nums[2] 4 4 - nums[4] 2 (重复) 2 - nums[2] 4 (进入环) ... 链表结构: 0 - 1 - 3 - 2 - 4 ---- ↑ | ----------------| 环的入口是 2就是重复数3.2 算法流程图数组: [1, 3, 4, 2, 2]转换为链表: 0 - 1 - 3 - 2 - 4 - ↑ | | ------------------| 环的入口节点是 2重复数 ------------------------------------------------------------ | Phase 1: 检测环找相遇点 | ------------------------------------------------------------ 初始化: slow 0, fast 0 ------------------------------------------------------------ | 第一次迭代: | | slow nums[slow] nums[0] 1 | | fast nums[nums[fast]] nums[nums[0]] nums[1] 3 | | slow1, fast3, 不相等继续 | ------------------------------------------------------------ slow fast 0 - 1 - 3 - 2 - 4 - ↑ | ------------ ------------------------------------------------------------ | 第二次迭代: | | slow nums[slow] nums[1] 3 | | fast nums[nums[fast]] nums[nums[3]] nums[2] 4 | | slow3, fast4, 不相等继续 | ------------------------------------------------------------ slow fast 0 - 1 - 3 - 2 - 4 - ↑ | ------------ ------------------------------------------------------------ | 第三次迭代: | | slow nums[slow] nums[3] 2 | | fast nums[nums[fast]] nums[nums[4]] nums[2] 4 | | slow2, fast4, 不相等继续 | ------------------------------------------------------------ slow fast 0 - 1 - 3 - 2 - 4 - ↑ | ------------ ------------------------------------------------------------ | 第四次迭代: | | slow nums[slow] nums[2] 4 | | fast nums[nums[fast]] nums[nums[4]] nums[2] 4 | | slow4, fast4, 相等找到相遇点 | ------------------------------------------------------------ slow/fast 0 - 1 - 3 - 2 - 4 - ↑ | ------------ Phase 1 完成: slow 和 fast 在节点 4 相遇 ------------------------------------------------------------ | Phase 2: 找环入口入口就是重复数 | ------------------------------------------------------------ 初始化: slow 0 (从起点开始) fast 4 (从相遇点开始) ------------------------------------------------------------ | 第一次迭代: | | slow nums[slow] nums[0] 1 | | fast nums[fast] nums[4] 2 | | slow1, fast2, 不相等 | ------------------------------------------------------------ slow fast 0 - 1 - 3 - 2 - 4 - ↑ | ------------ ------------------------------------------------------------ | 第二次迭代: | | slow nums[slow] nums[1] 3 | | fast nums[fast] nums[2] 4 | | slow3, fast4, 不相等 | ------------------------------------------------------------ slow fast 0 - 1 - 3 - 2 - 4 - ↑ | ------------ ------------------------------------------------------------ | 第三次迭代: | | slow nums[slow] nums[3] 2 | | fast nums[fast] nums[4] 2 | | slow2, fast2, 相等找到环入口 | ------------------------------------------------------------ slow/fast 0 - 1 - 3 - 2 - 4 - ↑ | ------------ 答案: slow 2即重复数3.3 完整代码slow版本classSolution{public:intfindDuplicate(vectorintnums){intslow0,fast0;// Phase 1: 找相遇点while(1){slownums[slow];fastnums[nums[fast]];if(slowfast)break;}// Phase 2: 找环入口inthead0;while(slow!head){slownums[slow];headnums[head];}returnslow;}};3.4 代码逐行解析Phase 1: 检测环intslow0,fast0;while(1){slownums[slow];// 慢指针走一步fastnums[nums[fast]];// 快指针走两步if(slowfast)break;// 相遇说明有环}慢指针每次走一步快指针每次走两步如果有环快慢指针一定会相遇Phase 2: 找环入口inthead0;while(slow!head){slownums[slow];headnums[head];}环入口的数学性质起点到入口的距离 相遇点到入口的距离让一个指针从起点开始一个从相遇点开始每次走一步再次相遇时就是环入口3.5 数学证明理解要点设: 起点到环入口的距离 F 环入口到相遇点的距离 a 环周长 C Phase 1: 慢指针走的距离 F a 快指针走的距离 F a nC (n 1) 快指针速度是慢指针的2倍: 2(F a) F a nC F a nC 相遇时: n 1所以 F a C Phase 2: 从起点到环入口距离 F 从相遇点到环入口距离 C - a 相遇点到环入口 (nC - F) - a (n-1)C (C - a - F) 如果 n 1: F a C, 所以 C - a F 所以从相遇点和从起点出发的指针会在环入口相遇3.6 复杂度分析复杂度值说明时间O(n)Phase 1 和 Phase 2 各 O(n)空间O(1)只用两个指针变量四、方法二二分查找4.1 核心思想基于抽屉原理鸽巢原理数组值在[1, n]范围如果小于等于mid的数字出现超过mid次则重复数一定在[1, mid]区间4.2 算法流程图数组: [1, 3, 4, 2, 2], n 5 初始: left 1, right 5 ------------------------------------------------------------ | mid 3, 统计 3 的元素个数 | | 3 的元素: 1, 3, 2, 2 | | count 4 | | count(3) 4 mid(3), 超过说明重复数 3 | | right mid 3 | ------------------------------------------------------------ ------------------------------------------------------------ | mid 2, 统计 2 的元素个数 | | 2 的元素: 1, 2, 2 | | count 3 | | count(2) 3 mid(2), 超过说明重复数 2 | | right mid 2 | ------------------------------------------------------------ ------------------------------------------------------------ | mid 1, 统计 1 的元素个数 | | 1 的元素: 1 | | count 1 | | count(1) 1 不大于 mid(1), 没超过说明重复数 1 | | left mid 1 2 | ------------------------------------------------------------ left2, right2 - 答案 24.3 完整代码classSolution{public:intfindDuplicate(vectorintnums){intleft1,rightnums.size()-1;while(leftright){intmidleft(right-left)/2;intcount0;// 统计 mid 的元素个数for(intnum:nums){if(nummid){count;}}// 如果 count mid说明重复数在 [1, mid]if(countmid){rightmid;}else{// 否则重复数在 [mid1, right]leftmid1;}}returnleft;}};4.4 复杂度分析复杂度值说明时间O(n log n)每次统计 O(n)二分 log n 次空间O(1)只用常数个变量五、方法三位运算5.1 核心思想统计每一位上 1 出现的次数如果某一位上 1 的出现次数超过 n/2说明这一位对重复数有贡献通过逐位确定得到重复数5.2 算法流程图数组: [1, 3, 4, 2, 2], n 5, 重复数 2 (二进制 010) 统计每一位: ------------------------------------------------------------ | 第0位: | | 数组中第0位为1的数: 1(1), 3(1) | | 1出现次数 2 | | 正常应该 5/2 2.5所以2次是正常的 | ------------------------------------------------------------ ------------------------------------------------------------ | 第1位: | | 数组中第1位为1的数: 2(1), 3(1), 2(1) | | 1出现次数 3 | | 正常应该 5/2 2.53 2.5说明重复数的第1位是1 | ------------------------------------------------------------ ------------------------------------------------------------ | 第2位: | | 数组中第2位为1的数: 4(1) | | 1出现次数 1 | | 正常应该 2.51 2.5说明重复数的第2位是0 | ------------------------------------------------------------ 得到: 重复数 010 25.3 完整代码classSolution{public:intfindDuplicate(vectorintnums){intnnums.size();intans0;// 统计每一位for(intbit0;bit31;bit){intcount0;intmask1bit;for(intnum:nums){if(nummask){count;}}// 如果 count n/2说明这一位是 1if(countn/2){ans|mask;}}returnans;}};5.4 复杂度分析复杂度值说明时间O(n * 31) ≈ O(n)统计 31 位空间O(1)只用常数个变量六、方法对比总结方法时间复杂度空间复杂度推荐指数Floyd 判圈O(n)O(1)★★★★★二分查找O(n log n)O(1)★★★★☆位运算O(n)O(1)★★★☆☆哈希表O(n)O(n)★☆☆☆☆Floyd 判圈的优势 1. O(1) 空间不修改数组 2. 时间复杂度 O(n) 3. 代码简洁 4. 体现数学思维环形链表检测 为什么快慢指针能检测环 - 快指针走两步慢指针走一步 - 如果有环快慢指针一定相遇 - 数学保证七、面试追问 FAQ问题回答Q: 为什么快慢指针一定会相遇快慢指针速度差为1在环中相当于相对速度为1一定会追上Q: 为什么从相遇点和从起点出发的指针会在环入口相遇数学性质起点到入口的距离 相遇点到入口的距离相位差Q: 为什么数组值可以作为下一个索引因为数组值在 [1,n] 范围且数组长度为 n1所以值总是一个有效索引Q: 如果有多个重复数怎么办Floyd 算法仍然能找到环入口但可能不是题目要求的那个Q: 二分查找的抽屉原理怎么理解如果每个数最多出现一次则 mid 的数最多有 mid 个超过就说明有重复Q: 位运算方法的时间复杂度O(32n) O(n)常数因子大八、相关题目题目难度关键点287. 寻找重复数中等Floyd 判圈 / 二分142. 环形链表 II中等Floyd 判圈求环入口141. 环形链表简单Floyd 判圈检测环136. 只出现一次的数字简单异或运算268. 丢失的数字简单异或 / 数学公式九、总结要点说明核心思想将数组转化为环形链表找环入口Phase 1快慢指针检测环找相遇点Phase 2从起点和相遇点同时出发在环入口相遇二分法基于抽屉原理统计 mid 的元素个数时间复杂度O(n)空间复杂度O(1)关键性质数组值作为索引 - 隐式链表结构
