树莓派与Blynk物联网平台实现伺服电机远程控制实践
2026/6/4 21:56:05
在算法面试中，有一道经典题目“寻找重复数”（Find the Duplicate Number）经常出现。它看似简单，却隐藏着多种巧妙的解法，并且对时间复杂度和空间复杂度都有苛刻的要求。本文将从题目出发，逐步分析三种不同的解法，并总结它们各自适用的场景。
题目描述
给定一个包含n + 1个整数的数组nums，其中每个整数都在[1, n]范围内（包括 1 和 n）。由于有n+1个数却只有n种取值，根据鸽巢原理，至少有一个整数出现了两次或更多次。假设数组中只有一个重复的整数（可能重复多次），要求找出这个重复的数。
附加要求：
不能修改原数组
只能使用常量级
O(1)的额外空间进阶：能否实现
O(n)的时间复杂度？
示例：
输入：nums = [1,3,4,2,2] → 输出：2 输入：nums = [3,1,3,4,2] → 输出：3 输入：nums = [3,3,3,3,3] → 输出：3解法一：排序后比较相邻元素
核心思想
如果数组是有序的，那么相同的数字一定会紧挨在一起。例如[1,2,2,3,4]中，两个2相邻。我们只需要遍历一遍，发现nums[i] === nums[i-1]就找到了重复数。
详细步骤
对原数组进行升序排序（例如 JavaScript 的
sort）。从索引
1开始遍历数组。如果当前元素和前一个元素相等，则当前元素就是重复的数，直接返回。
示例演示
输入：[3,1,3,4,2]
排序后 →
[1,2,3,3,4]遍历：比较
1和2？不等。2和3？不等。3和3？相等 → 返回3。
代码
var findDuplicate = function(nums) { nums.sort((a, b) => a - b); for (let i = 1; i < nums.length; i++) { if (nums[i] === nums[i - 1]) { return nums[i]; } } };复杂度分析
时间复杂度：
O(n log n)，排序是主要开销。空间复杂度：
O(1)（如果排序算法是原地排序，JS 的sort一般是原地排序）。
优缺点与适用场景
| 优点 | 缺点 | 适用场景 |
|---|---|---|
| 思路极其简单，代码量少 | 修改了原数组（不符合题目要求） | 题目允许修改数组，且对时间复杂度不苛刻时 |
⚠️ 注意：本题明确要求不能修改原数组，因此排序法实际上不符合题意。这里讲解它是为了对比，也是大多数人的第一反应。
解法二：二分查找（基于值域）
核心思想
我们不直接对数组下标二分，而是对数值范围[1, n]进行二分。
统计数组中有多少个数<= mid，记作count。
根据鸽巢原理：如果count > mid，说明重复的数字一定在左半区间[left, mid]中；否则在右半区间[mid+1, right]中。
为什么count > mid就说明重复数在左边？
假设没有重复，数值1到mid最多只能出现mid次（每个数最多一次）。如果实际上出现了超过mid次，那么必然有某个数出现了多次，这个数肯定在1..mid范围内。
详细步骤
初始化
left = 1，right = n（n = nums.length - 1）。当
left <= right时循环：计算
mid = floor((left + right) / 2)。遍历整个数组，统计
nums[i] <= mid的个数count。如果
count <= mid，则重复数不在[left, mid]中，令left = mid + 1。否则
count > mid，则重复数在[left, mid]中，记录ans = mid，并令right = mid - 1向左缩小范围。
返回
ans。
示例演示
输入：nums = [1,3,4,2,2]，n = 4
left=1, right=4, mid=2
统计 ≤2 的数：[1,2,2]→ count = 33 > 2→ 重复数在[1,2]，ans=2，right=1left=1, right=1, mid=1
统计 ≤1 的数：[1]→ count = 11 ≤ 1→ 重复数不在左半边，left=2循环结束，返回
ans = 2✅
代码
var findDuplicate = function(nums) { let n = nums.length - 1; // 数值范围 1~n let left = 1, right = n; let ans = -1; while (left <= right) { let mid = Math.floor((left + right) / 2); let count = 0; for (let i = 0; i <= n; i++) { if (nums[i] <= mid) count++; } if (count <= mid) { left = mid + 1; } else { ans = mid; right = mid - 1; } } return ans; };复杂度分析
时间复杂度：
O(n log n)。二分需要log n轮，每轮遍历整个数组O(n)。空间复杂度：
O(1)。
优缺点与适用场景
| 优点 | 缺点 | 适用场景 |
|---|---|---|
| 不修改原数组，符合基本要求 | 时间复杂度O(n log n)不是最优 | 值域范围已知且有界，需要不修改数组，可接受O(n log n)时间 |
这种值域二分技巧非常经典，还可以解决“寻找缺失的第一个正数”等问题。
解法三：快慢指针（Floyd 判圈算法）
核心思想
将数组视为一个隐式链表：每个索引i看作一个节点，nums[i]表示该节点指向的下一个节点索引。例如nums = [1,3,4,2,2]：
索引 0 → 指向索引 1（因为
nums[0] = 1）索引 1 → 指向索引 3（因为
nums[1] = 3）索引 2 → 指向索引 4（因为
nums[2] = 4）索引 3 → 指向索引 2（因为
nums[3] = 2）索引 4 → 指向索引 2（因为
nums[4] = 2）
画出链：0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 -> ...，可以看到2 -> 4 -> 2形成了一个环。
为什么一定有环？
因为每个节点i的nums[i]取值在[1, n]之间，而索引范围是[0, n]。0作为起点，任何nums[i]都不等于0（因为取值从1开始），所以从0出发永远不会回到0。又因为总共有n+1个节点，但有效取值只有n种，根据鸽巢原理，一定会访问到重复的节点，形成环。环的入口就是那个重复的数字。
详细步骤（Floyd 判圈算法）
第一次相遇：
慢指针slow每次走一步：slow = nums[slow]
快指针fast每次走两步：fast = nums[nums[fast]]
它们最终会在环内相遇（因为快指针每次多走一步，一定会追上慢指针）。找环入口：
将slow重置为起点0，fast留在相遇点。
然后两个指针每次都走一步：slow = nums[slow]，fast = nums[fast]。
它们再次相遇的位置就是环的入口，也就是重复的数字。
为什么第二次相遇点就是重复数？
设起点到环入口距离为a，环入口到相遇点距离为b，环的周长为c。
第一次相遇时，快指针走的路程是慢指针的 2 倍，可以推导出a和c-b的关系。将慢指针放回起点后，两者以相同速度前进，必然在环入口相遇。
这个数学推导略复杂，但可以简单记忆：第一次相遇后，慢指针回起点，两者同步走，再次相遇点即为环入口。
示例演示
nums = [1,3,4,2,2]，n=4
初始：
slow=0, fast=0第一轮：
slow = nums[0] = 1，fast = nums[nums[0]] = nums[1] = 3第二轮：
slow = nums[1] = 3，fast = nums[nums[3]] = nums[2] = 4第三轮：
slow = nums[3] = 2，fast = nums[nums[4]] = nums[2] = 4第四轮：
slow = nums[2] = 4，fast = nums[nums[4]] = nums[2] = 4→ 相遇在索引4
此时slow=4, fast=4。
重置slow = 0，fast = 4：
第一轮：
slow = nums[0] = 1，fast = nums[4] = 2第二轮：
slow = nums[1] = 3，fast = nums[2] = 4第三轮：
slow = nums[3] = 2，fast = nums[4] = 2→ 相遇在索引2
nums[2] = 2，所以重复数是2✅
代码
var findDuplicate = function(nums) { let slow = 0, fast = 0; // 第一次相遇 do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow !== fast); // 找环入口 slow = 0; while (slow !== fast) { slow = nums[slow]; fast = nums[fast]; } return slow; };复杂度分析
时间复杂度：
O(n)。慢指针最多走O(n)步，快指针也最多O(n)步。空间复杂度：
O(1)。
优缺点与适用场景
| 优点 | 缺点 | 适用场景 |
|---|---|---|
时间复杂度最优O(n)，空间O(1)，不修改数组 | 思路较巧妙，需要理解链表判环 | 完美满足本题所有要求，面试最优解 |
只要你能将数组与索引映射成链表（并且保证起点不在环内），快慢指针就是最强解法。
三种解法总结对比
| 解法 | 时间复杂度 | 空间复杂度 | 是否修改数组 | 理解难度 | 适用场景 |
|---|---|---|---|---|---|
| 排序法 | O(n log n) | O(1) | 是 | 低 | 允许修改数组，追求代码简单 |
| 二分查找 | O(n log n) | O(1) | 否 | 中 | 不修改数组，值域有界，可接受 O(n log n) |
| 快慢指针 | O(n) | O(1) | 否 | 较高 | 不修改数组，要求线性时间，面试最优解 |
常见问题 FAQ
Q1：为什么快慢指针第一次相遇后，慢指针回到起点，两者再次相遇点就是重复数？
A：这是 Floyd 判圈算法的标准结论。可以简单理解为：从起点到环入口的距离 ＝ 相遇点到环入口的距离（绕环方向）。两者以相同速度前进，必然在环入口碰头。
Q2：二分查找中为什么 count > mid 就能确定重复数在左边？
A：如果没有重复，1..mid这些数字每个最多出现一次，总数不会超过mid。现在实际个数大于mid，说明至少有一个数字出现了两次以上，且这个数字必然 ≤ mid，因此重复数在左半区间。
Q3：快慢指针解法如何保证不越界？
A：因为nums[i]范围是[1, n]，而数组长度是n+1，索引范围[0, n]，所以nums[nums[i]]一定在[1, n]范围内，不会越界。
结语
“寻找重复数”是一道构思精巧的题目，它展示了同一个问题在不同约束下可以演变出多种不同复杂度的解法。从最简单的排序到利用值域的二分解法，再到将数组视为链表的快慢指针，每一步都体现了算法设计中的巧妙思想。
下次当你遇到类似的问题时，可以根据题目是否允许修改数组、是否对时间复杂度有严格要求，来选择最合适的解法。
如果只关心功能，排序法足够快写。
如果要求不修改数组但可以接受
O(n log n)，二分查找是稳妥选择。如果追求极致效率，别忘了快慢指针这个“大杀器”。
希望这篇文章能帮助你彻底掌握这道经典题目。欢迎在评论区留言讨论！