【leetcode刷题】T54-寻找重复数
【题目】
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2]
输出: 3
说明：
- 不能更改原数组（假设数组是只读的）。
- 只能使用额外的 O(1) 的空间。
- 时间复杂度小于 O(n^2) 。
- 数组中只有一个重复的数字，但它可能不止重复出现一次。
【思路】
暴力破解，遍历元素，判断是否在数组中存在，时间复杂度为O(n^2)，不满足要求。
使用hash，空间复杂度为O(n)，不满足要求。
苍天呀，这题不是在危难我们吗？
只遍历一次，用O(n)的时间，似乎完成不了。
时间复杂度要求小于O(n^2)，那么似乎时间复杂度是O(n * lg n)。
使用二分查找？好像可以解决问题。
对于一个数num，数组中小于等于该数的元素个数为count，当count<=num时，说明大于num的元素个数大于n-num个，num+1 -> n当中有元素重复；反之，l -> num-1当中有元素重复。
这样，问题就变成了，我们需要找到一个数num，这个数需要满足的条件是：数组中小于等于num的元素个数大于num，同时数组中小于等于num-1的元素个数小于num。
有其他方法吗？
没有。
这是不可能的。
有人将这个问题转换为寻找有环链表中环入口这个问题。比如，数组[1, 5, 2, 1, 4, 3]可将下标和元素转换为0->1，1->5，2->2，3->1，4->4，5->3，从而得到有环链表0->1->5->3->1。
那么如何找到环入口呢？
分为两步：一是使用快指针每次前进两步，慢指针每次前进一步，直到他们相遇；二是慢指针重新回到第一个元素，快慢指针每次前进一步，直到他们相遇。第二步的相遇点即为环入口，即重复元素。
为什么可以呢？
如图所示，开始位置到环入口距离为a，环入口到相遇点距离为b，相遇点到环入口距离为c。
那么第一次相遇时，假设慢指针走了k1圈，则走的总距离为x1 = a + b + k1 * (b+c)；
假设快指针走了k2圈，则走的总距离为x2 = a + b + k2 * (b+c)；
由于快指针速度是慢指针的两倍，则x2-x1 = (k2-k1) * (b+c) = a + b + k1 * (b+c)
得到 a = (k2 - 2*k1) * (b+c) - b，即是，慢指针从头开始走，快指针从相遇点开始走，两指针都是每次走一步，那么下一次相遇点即为环入口。
【代码】
python版本
方法一
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l, r = , len(nums) -
while l <= r:
mid = (l + r) //
count =
for n in nums:
if n <= mid:
count +=
# mid -> n元素过多
if count <= mid:
l = mid +
# l -> mid元素过多
else:
r = mid -
return l
方法二
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
first = nums[]
second = nums[nums[]]
# 找到相遇点
while first != second:
first = nums[first]
second = nums[nums[second]]
# 找到环入口
first =
while first != second:
first = nums[first]
second = nums[second]
return first
C++版本
方法一
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int l=, r=nums.size()-1;
int mid=;
int count=;
while(l <= r){
mid = (l + r) / ;
count = ;
for(auto n: nums){
if(n <= mid)
count++;
}
// mid->r元素过多
if(count <= mid)
l = mid + ;
// l->mid元素过多
else
r = mid - ;
}
// 最后，<=r的元素个数合适，<=l的元素个数较多
return l;
}
};
方法二
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int first=, second=;
// 找到相遇点
do{
first = nums[first];
second = nums[nums[second]];
}while(first != second);
// 找到环入口
first = ;
while(first != second){
first = nums[first];
second = nums[second];
}
return first;
}
};