每日算法系列【LeetCode 287】寻找重复数
每日算法系列【LeetCode 287】寻找重复数
题目描述
给定一个包含 个整数的数组 ，其数字都在 到 之间（包括 和 ），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
说明
- 不能更改原数组（假设数组是只读的）。
- 只能使用额外的 的空间。
- 时间复杂度小于 。
- 数组中只有一个重复的数字，但它可能不止重复出现一次。
示例1
输入：
[1,3,4,2,2]
输出：
2示例2
输入：
[3,1,3,4,2]
输出：
3题解
二分法
根据抽屉原理，如果大小为 的抽屉里放了大于 个数，那么一定有一个抽屉里至少放了两个数。
那我们不妨统计一下数组中有多少个数满足 ，数量记为 。
如果 ，那么根据抽屉原理， 到 中一定有一个数出现了至少两次。
反之如果 ，那么说明满足 的数的数量是 ，而抽屉大小是 ，所以根据抽屉原理， 到 中一定有一个数出现了至少两次。
综上，可以采用二分法，不断缩小 的范围，最终得到这个出现至少两次的数的值。
时间复杂度 。
快慢指针法
因为 中数据范围是 到 ，所以 。那么接着用 作为下标来索引值，得到 。如果 已经出现过了 ，那么重复值已经找到了。否则的话 还没出现过的话，继续用 作为下标来索引，直到出现重复值。
可以发现按照这种方法索引下去，形成了一个链，也就是 。最终这条链末端一定会产生出一个环，那么环的入口一定就是那个重复的数。
举个例子，如下图所示，最终环产生在了 上面，而 又是链进入环的入口，所以重复的数就是 。
那么如何求链表中的环呢？这其实是一道面试经常会问到的经典题，标准解法就是用两个快慢指针。
初始时两个指针指着链表头结点，然后同时移动。慢指针一次移动一个结点，快指针一次移动两个结点。当下一次快指针又和慢指针相遇时，停止移动。然后用第三个指针指着头结点，慢指针留在原地，两者同时移动，都是一次移动一个结点，直到相遇。这时两者指着的结点就是环的入口了。
大家可以用上面的例子自己画图演示一下，我下面严格证明一下为什么这样是对的。
假设如下图所示，链表中链的长度是 ，环的长度是 。
假设慢指针和快指针第一次相遇时，慢指针移动的距离是 ，那么快指针移动距离就是 。
可以列出等式 ，也就是两者距离差值一定是环长度的正整数 倍，同时 是使得 的最小正整数，即 。这时候慢指针离入口的距离是 ，也就是说，慢指针只需要再多绕 个环的长度，就能恰好和从头结点而来的指针相遇在入口处。
时间复杂度 O(n) 。
扩展：
那有人可能会问了，那要是链最后回到了 ，不就没有链，只有环了吗？哪来的入口？这是对的，所以本题中限制了 数组里都是大于 的，如果范围是 到 的话，不能直接用数值但下标索引了，不然会出现下面这种情况，也就是 也在环里了。
其实这种情况我们只需要稍稍修改一下索引，让 不可能出现在环里就行了，也就是让 当作索引，如下图所示。最终重复的数只需要减去 就行了。
代码
二分法（c++）
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size() - 1;
int l = 1, r = n;
while (l < r) {
int m = l+(r-l)/2;
int cnt = 0;
for (int i = 0; i < n+1; ++i) {
if (nums[i] <= m) cnt++;
}
if (cnt > m) r = m;
else l = m + 1;
}
return l;
}
};快慢指针法（c++）
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = 0, fast = 0;
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast) break;
}
int find = 0;
while (find != slow) {
slow = nums[slow];
find = nums[find];
}
return find;
}
};二分法（python）
class Solution:
def findDuplicate(self, nums):
n = len(nums) - 1
l, r = 1, n
while l < r:
m = l+(r-l)//2
cnt = sum([x<=m for x in nums])
if cnt > m:
r = m
else:
l = m + 1
return l快慢指针法（python）
class Solution:
def findDuplicate(self, nums):
slow, fast = 0, 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
find = 0
while find != slow:
slow = nums[slow]
find = nums[find]
return find作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~