一个长度为 n + 1 的整形数组，其中的数字都在 1 到 n 之间，包括 1 和 n ，可知至少有一个重复的数字存在。假设只有一个数字重复，找出这个重复的数字。
注意：
1.不能更改数组内容（假设数组是只读的）。
2.只能使用恒定的额外空间，即要求空间复杂度是 O(1) 。
3.时间复杂度小于 O(n2)
4.数组中只有一个数字重复，但它可能不止一次重复出现。
f1//时间复杂度O(n)，空间复杂度O(1)，不用移动原数组，需要改动原数组。
class Solution {
public:
int findDuplicate(vector<int>& nums) {
// 标记法：我们可以看到，其实在nums[n + 1]中，因为数字都是在1到n之内，所以nums[i]就像一个个指针，指着另外的位置上的数字。
// 有一个巧妙的办法是，我们遍历一遍数字，把nums[i]指向的数（即nums[nums[i]]）做一个+n的操作，那么如果遇到一个nums[nums[i]]的值已经大于n了，
// 说明这个数已经被其他数字指到过了，也就是找到了重复值。在执行的过程中，我们还要先判断一下nums[i]是否大于n（因为可能先前被别人指过所以+n了），用一个值来保存其原来的值。
int n = nums.size();
for (int i = 0; i < n; ++i){
// nums[i] - 1表示next一定能和下标进行一一对应
int next = nums[i] - 1;
// 因为每次循环只有两个数存在，所以如果该数刚好被next指针标记过，则需要将next指针还原到原来的状态，防止溢出
if (nums[i] > n)
next -= n;
// 如果发现标记指针的值已经大于n，说明该值呗重复标记
if (nums[next] > n)
return next + 1;
// 否则对已经检查的值进行标记
else
nums[next] += n;
}
return -1;
}
};
f2//时间复杂度O(nlogn)，空间复杂度O(1)，不用移动原数组，不用改动原数组。
这个是二分查找，直接看代码也可以理解
int findDuplicate5(vector<int> nums) {
int n = nums.size();
int left = 1, right = n;
int mid, count;
while (left < right)
{
count = 0;
mid = (left + right) / 2;
// 计数
for (int i = 0; i < n; ++i)
{
if (nums[i] >= left && nums[i] <= mid)
++count;
}
// 二分法循环找出出现循环的数
//这里为什么是mid+1，因为考虑到奇偶数，所以mid+1不论奇偶数都可以作为判定条件，而不会漏掉
if (left + count > mid + 1)
right = mid;
else
left = mid + 1;
}
return left;
}
f3//时间复杂度O(n)，空间复杂度O(1)，不用移动原数组，不用改动原数组。
image.png
为什么本题能抽象为一个链表找环的问题？一定会有环的存在吗？一定会有环外的p的部分吗？
因为有重复的数，而重复的数字一定是环的入口。这里不需要考虑环的个数，只要检测到环并找到入口即可。
class Solution {
public:
int findDuplicate(vector<int> nums) {
int slow = 0;
int fast = 0;
do{
// slow相当于next-》
// fast相当于next->next->
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// 当两次相遇时，slow走了p+c，fast走了p+c+k*l
// 将两个步长调整为一致
// slow = slow->next
// fast = fast->next
// 将fast置为起点出，这样，当fast走了P+c后，slow走了K*L，因为k*l，所以slow一定回到出发点，两个指针相交
// 此时指向的元素为重复数的值
fast = 0;
while (fast != slow){
fast = nums[fast];
slow = nums[slow];
}
return fast;
}
};
给出对应的python代码
class Solution:
# @param num, a list of integer
# @return an integer
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
slow = nums[0]
fast = nums[nums[0]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
fast = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
if __name__ == "__main__":
print(Solution().findDuplicate([1,2,3,4,4]))
