Java版LeetCode热题100之寻找重复数：深入解析与实战应用

Java版LeetCode热题100之寻找重复数：深入解析与实战应用

本文目标：全面、系统地讲解 LeetCode 第287题「寻找重复数」（Find the Duplicate Number），从题目理解、多种解法推导、代码实现到面试技巧和实际应用场景，帮助你真正掌握这道高频且极具深度的算法题。

一、原题回顾

题目描述

给定一个包含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 <= 10^5
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums中只有一个整数出现两次或多次，其余整数均只出现一次

进阶挑战

1. 如何证明nums中至少存在一个重复的数字？
2. 你能设计一个线性时间复杂度 O(n)的解决方案吗？

二、原题分析

核心矛盾点

这道题看似简单，但约束条件极其苛刻：

✅ 必须在不修改数组 + O(1) 空间下找到重复数。

数学证明：为何必有重复？

这是经典的鸽巢原理（Pigeonhole Principle）：

• 有n+1个“鸽子”（数组元素）
• 只有n个“鸽巢”（数字 1 到 n）
• 因此至少有一个鸽巢中有 ≥2 只鸽子 →必有重复

这是题目成立的理论基础。

问题本质

将数组视为一种隐式映射关系：

• 索引i ∈ [0, n]
• 值nums[i] ∈ [1, n]

由于值域大小为n，而索引有n+1个，必然存在多个索引指向同一个值，即重复。

三、答案构思

我们可以从多个角度突破约束：

思路1：二分查找（基于计数）

• 核心思想：利用“重复数”的性质——它会导致某些区间的计数异常。
• 定义cnt(x) = nums 中 ≤ x 的元素个数
• 若无重复，则cnt(x) = x
• 若有重复数target，则：
  • 当x < target时，cnt(x) ≤ x
  • 当x ≥ target时，cnt(x) > x
• 具有单调性，可用二分查找。

✅ 满足 O(1) 空间
⚠️ 时间复杂度 O(n log n)

思路2：位运算法（按位统计）

• 核心思想：比较nums与理想集合[1, n]在每一位上 1 的个数。
• 对于第k位：
  • 若nums中该位为 1 的数量 >[1,n]中的数量 → 重复数该位为 1
• 按位还原重复数。

✅ 满足 O(1) 空间
⚠️ 时间复杂度 O(n log n)

思路3：快慢指针（Floyd 判圈算法）—最优解

• 核心思想：将数组视为链表，i → nums[i]构成指针。
• 由于存在重复数，必有环，且环的入口即为重复数。
• 使用 Floyd 算法找环入口。

✅时间 O(n)，空间 O(1)，满足进阶要求
✅ 是面试官最希望看到的解法

四、完整答案（Java实现）

下面提供三种主流解法的完整代码，并附详细注释。

解法一：二分查找（基于计数）

classSolution{publicintfindDuplicate(int[]nums){intn=nums.length;// n+1 个元素，值域 [1, n]intleft=1,right=n-1;// 值域是 [1, n]，但 n = nums.length - 1intans=-1;while(left<=right){intmid=left+(right-left)/2;// 统计 nums 中 <= mid 的元素个数intcount=0;for(intnum:nums){if(num<=mid){count++;}}if(count<=mid){// 说明重复数在 [mid+1, right]left=mid+1;}else{// 说明重复数在 [left, mid]ans=mid;right=mid-1;}}returnans;}}

✅ 正确性依赖于单调性
⚠️ 注意：right = n - 1，因为n = nums.length，值域最大为n-1

解法二：位运算法（按位统计）

classSolution{publicintfindDuplicate(int[]nums){intn=nums.length;// n = original_n + 1intoriginalN=n-1;// 真实的 n// 确定需要检查的最高位intbitMax=31;while(((originalN)>>bitMax)==0){bitMax--;}intresult=0;// 检查每一位for(intbit=0;bit<=bitMax;bit++){intx=0;// nums 中第 bit 位为 1 的个数inty=0;// [1, originalN] 中第 bit 位为 1 的个数for(intnum:nums){if((num&(1<<bit))!=0){x++;}}for(inti=1;i<=originalN;i++){if((i&(1<<bit))!=0){y++;}}// 如果 x > y，说明重复数该位为 1if(x>y){result|=(1<<bit);}}returnresult;}}

✅ 巧妙利用位运算
⚠️ 注意：i从 1 开始，到originalN = n-1

解法三：快慢指针（Floyd 判圈算法）—推荐

classSolution{publicintfindDuplicate(int[]nums){// 第一阶段：快慢指针找相遇点intslow=nums[0];intfast=nums[0];// 注意：必须先走再判断，避免初始相等do{slow=nums[slow];// 慢指针走一步fast=nums[nums[fast]];// 快指针走两步}while(slow!=fast);// 第二阶段：找环入口slow=nums[0];// 慢指针回到起点while(slow!=fast){slow=nums[slow];fast=nums[fast];}returnslow;// 或 fast，两者相等}}

✅时间 O(n)，空间 O(1)
✅ 是本题的最优解，也是面试高频考点

五、代码分析

我们重点分析快慢指针法（解法三）：

为什么能建模为链表？

• 将数组索引视为节点，nums[i]视为i的 next 指针。
• 例如nums = [1,3,4,2,2]：
  • 0 → 1 → 3 → 2 → 4 → 2 → 4 → …
  • 形成环：2 → 4 → 2

为什么环的入口是重复数？

• 重复数target被多个索引指向（如索引 2 和 4 都指向 2）
• 因此target是第一个被多次访问的节点，即环的入口。

Floyd 算法原理

设：

• a= 起点到环入口的距离
• b= 环入口到相遇点的距离
• c= 相遇点到环入口的距离（b + c = L，L 为环长）

慢指针走a + b，快指针走2(a + b) = a + b + kL
→a + b = kL→a = kL - b = (k-1)L + c

因此，当慢指针从起点走a步，快指针从相遇点走c步（加若干圈），两者在环入口相遇。

六、时间复杂度与空间复杂度分析

详细说明

• 快慢指针：
  • 第一阶段：最多走 2n 步（快指针）
  • 第二阶段：最多走 n 步
  • 总计 O(n)
• 二分/位运算：
  • 外层循环 O(log n)（数值范围）
  • 内层遍历 O(n)
  • 总计 O(n log n)

💡快慢指针是唯一满足“线性时间 + 常数空间”的解法

七、常见问题解答（FAQ）

Q1：为什么快慢指针初始值设为nums[0]而不是 0？

A：因为我们的“链表”是从索引 0 开始的，nums[0]是第一个节点的值。
若设为 0，会错误地将索引 0 视为值，而实际上值域是 [1, n]。

正确建模：节点 = 索引，指针 = nums[索引]

Q2：如果重复数出现超过两次，算法还正确吗？

A：完全正确。
无论重复多少次，只要存在重复，就必然形成环，且环入口仍是重复数。

例如nums = [3,3,3,3,3]：

• 0 → 3 → 3 → 3 → …
• 环入口是 3，正确。

Q3：能否用数学方法（如求和）解决？

A：不能。
设重复数为x，出现k次，则：

sum(nums) = (1+2+...+n) + (k-1)x

但有两个未知数x和k，无法求解。

Q4：为什么二分查找的右边界是n-1？

A：因为nums.length = n + 1，所以n = nums.length - 1。
值域是[1, n] = [1, nums.length - 1]。

八、优化思路

1. 快慢指针的初始化优化

可写为：

intslow=0,fast=0;do{slow=nums[slow];fast=nums[nums[fast]];}while(slow!=fast);

然后第二阶段slow = 0。

两种写法等价，后者更直观（起点为索引 0）。

2. 位运算的性能优化

预计算[1, n]的每一位 1 的个数，避免每次循环都计算：

// 预计算 yBits[bit] = [1, n] 中第 bit 位为 1 的个数int[]yBits=newint[32];for(inti=1;i<=originalN;i++){for(intbit=0;bit<=bitMax;bit++){if((i&(1<<bit))!=0){yBits[bit]++;}}}

但空间变为 O(log n)，违反 O(1) 要求，不推荐。

3. 早期终止（无实质收益）

无法提前终止，因为必须完成整个算法流程。

九、数据结构与算法基础知识点回顾

1. 鸽巢原理（Pigeonhole Principle）

• 若n+1个物品放入n个盒子，至少一个盒子有 ≥2 个物品。
• 应用于证明重复、哈希冲突等。

2. Floyd 判圈算法（龟兔赛跑）

• 用途：检测链表是否有环，并找环入口。
• 步骤：
  1. 快慢指针找相遇点
  2. 一指针回起点，同步走，相遇即入口
• 时间：O(n)，空间：O(1)

3. 二分查找的扩展应用

• 不仅用于有序数组，还可用于具有单调性的函数
• 本题中f(x) = (count(x) > x)是单调布尔函数

4. 位运算技巧

• x & (1 << k)：检查第 k 位是否为 1
• x |= (1 << k)：设置第 k 位为 1
• 用于按位统计、状态压缩等

5. 隐式图建模

• 将数组/函数视为图的邻接表
• 本题：f(i) = nums[i]构成函数图
• 应用于循环检测、拓扑排序等

十、面试官提问环节（模拟）

Q：你能解释为什么快慢指针一定能找到环吗？

答：
因为数组长度为n+1，值域为[1, n]，所以从任意起点出发，路径必然进入循环（有限状态机）。
快指针每次比慢指针多走一步，相对速度为 1，因此在环内最多L步就会相遇（L 为环长）。

Q：如果数组中有多个重复数怎么办？

答：
本题假设只有一个重复数。
若允许多个重复，快慢指针仍能找到一个环，但不一定是所有重复数。
此时需改用其他方法（如二分查找仍适用，但结果可能是任意一个重复数）。

Q：这个算法能处理负数吗？

答：
不能。本题约束nums[i] ∈ [1, n]，保证了nums[i]可作为有效索引。
若有负数或超范围值，建模会失败。

Q：为什么不能直接用 HashMap？

答：
虽然 HashMap 能在 O(n) 时间找到重复，但空间复杂度 O(n)，违反题目“O(1) 空间”要求。
面试中必须严格遵守约束条件。

十一、这道算法题在实际开发中的应用

1. 内存泄漏检测

在垃圾回收中，对象引用图可能形成环。Floyd 算法可用于检测循环引用，防止内存泄漏。

2. 数据校验

在数据库或文件系统中，ID 应唯一。若发现重复 ID，可用类似方法快速定位（在特定约束下）。

3. 随机数生成器测试

伪随机数生成器应避免短周期。通过将输出视为序列，用 Floyd 算法检测周期长度。

4. 网络协议中的环路检测

在路由协议中，数据包不应无限循环。可通过类似指针追踪检测环路。

5. 算法竞赛与系统设计

• 在 O(1) 空间限制下处理大数据
• 设计流式算法（streaming algorithm）
• 隐式图遍历（implicit graph traversal）

6. 密码学中的 Pollard’s Rho 算法

用于整数分解，核心就是 Floyd 判圈算法，通过函数迭代找碰撞。

十二、相关题目推荐

💡 建议：掌握本题后，重点练习142. 环形链表 II，它是本题的通用形式。

十三、总结与延伸

核心收获

1. 约束驱动设计：在严格限制下（不修改 + O(1) 空间），必须跳出常规思维。
2. 隐式建模能力：将数组视为函数图，是高级算法设计的关键。
3. Floyd 算法的威力：不仅用于链表，还可解决数组重复、随机数周期等问题。
4. 多种解法对比：理解不同方法的 trade-off（时间 vs 空间 vs 复杂度）。

延伸思考

Q：能否推广到找多个重复数？

A：在 O(1) 空间下极难。通常需要放松约束（如允许修改数组，用原地哈希）。

Q：如果重复数出现偶数次，能否用异或？

A：不能。异或只能处理“一个数出现奇数次，其余偶数次”的情况。本题重复次数 ≥2，且其他数只出现一次（奇数次），异或结果无意义。

Q：如何证明二分查找的单调性？

A：设无重复时cnt(x) = x。
加入重复数t后：

• 若x < t，cnt(x)不变 →cnt(x) = x
• 若x ≥ t，cnt(x)增加 →cnt(x) > x
  因此cnt(x) > x的最小x即为t。

面试建议

• 优先写出快慢指针解法，展示算法深度；
• 务必解释建模过程（数组 → 链表）；
• 手动画图演示Floyd 算法，增强说服力；
• 提及实际应用（如内存泄漏检测），体现工程思维。

结语：
“寻找重复数”是一道集数学、算法、工程于一体的经典题目。
它不仅考察编码能力，更考验抽象建模和约束优化的思维。
掌握它，你就掌握了在极端限制下解决问题的钥匙，也为更复杂的系统设计打下坚实基础。