tags: Array
#LeetCode 287 Find the Duplicate Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive),
prove that at least one duplicate number must exist.
Assume that there is only one duplicate number, find the duplicate one.
Question
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant,
O(1)extra space. - Your runtime complexity should be less than
O(n2). - There is only one duplicate number in the array, but it could be repeated more than once.
Diffculty
Medium
Similar Problems
题目要求我们不能改变原数组，即不能给原数组排序，又不能用多余空间，那么哈希表神马的也就不用考虑了， 又说时间小于O(n^2)，也就不能用brute force的方法。那么只能寻求 O(logn) 或者 O(N) 的解法了，下面是两种解法分析：
（1）第一个解法，涉及到鸽巢原理。 假设有n=10的一个数组（大小是n+1），那我目前的搜索范围是[1,10]，先找中间的数mid=5.现在我们遍历数组的所有元素并统计<=5的元素个数，记作n_lteq5好了，那么有： 如果n_lteq5>5，那就有6个数字占了本来只有5个的坑位，那目标数字肯定是在[1,5]的范围内了； 如果n_lteq5<=5，那前面的元素都挺守规矩的，得看看[6,10]里头哪个数字在作怪； 这样每一次判断，问题的规模都会缩小一半，一共n+1个数字，时间复杂度是O(nlogn)。
，那我们也就只能考虑用二分搜索法了， 我们在区间[1, n]中搜索，首先求出中点mid，然后遍历整个数组，统计所有小于等于mid的数的个数， 如果个数大于mid，则说明重复值在[mid+1, n]之间，反之，重复值应在[1, mid-1]之间， 然后依次类推，直到搜索完成，此时的low就是我们要求的重复值，
class Solution {
public:
int findDuplicate(vector<int>& A) {
int n = A.size();
int low = 1, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
int cnt = 0;
for (auto i : A) { // count the number of element that are smaller than mid
if (i <= mid) ++cnt;
}
if (cnt <= mid) low = mid + 1;
else high = mid - 1;
}
return low;
}
};第二个解法，把元素值放在以它为 index 的位置。
假设数组A长度是n, 里面存储1到n的整数，那么很清楚，我们可以在按照A[i] = i+1，进行排序。 但是现在有n+1个整数，而且至少有一个数字存在冗余。 如果我们仍然按照A[i] = i+1来排序数组的话，那么当发现A[i]上已经是i+1的值时，说明我们已经找到了冗余数了。
举个例子，
i
3 1 2 1 -----> 2 1 3 1 -----> 1 2 3 1 ---->
A[0] != 1 still A[0] != 1 now A[0] == 1
swap(A[0], A[A[0]]) swap(A[0], A[A[0]]) move to next
1 2 3 1 -----> 1 2 3 1 -----> 1 2 3 1
A[1] == 2 A[2] == 3 A[3] != 4, need to swap(A[3], A[A[3]])
move to next move to next but A[A[3]] alread has right value, so A[3] is the duplicate number
简单的说，就是遍历数组的同时，某个元素应该放在这个元素值所在的坐标上去， 也即按照 A[i] 应该放到 A[A[i]] 原则，进行swap，第一个无法swap的数字就是所求。
注意，由于这里的数字序列是 1 到 n，所以应该是 A[i] 放到 A[A[i] - 1]。
class Solution {
public:
int findDuplicate(vector<int>& A) {
int length = A.size();
for (int i = 0; i < (int)a.size(); ++i) {
while (i != a[i] - 1) {
if (a[a[i] - 1] == a[i]) { // 如果要放的位置上的元素跟 A[i] 相同，说明有重复
return a[i];
}
swap(a[i], a[a[i] - 1]);
}
}
return -1;
}
};还有一个大神的解法，也是 O(N)。 其核心思想快慢指针在之前的题目 Linked List Cycle II 中就有应用，这里应用的更加巧妙一些，由于题目限定了区间 [1,n]，所以可以巧妙的利用坐标和数值之间相互转换，而由于重复数字的存在，那么一定会形成环，我们用快慢指针可以找到环并确定环的起始位置，确实是太巧妙了！ 链接
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = 0, fast = 0, t = 0;
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast) break;
}
while (true) {
slow = nums[slow];
t = nums[t];
if (slow == t) break;
}
return slow;
}
};
class Solution {
public:
int findDuplicate(const vector<int>& A) {
int n = A.size();
int result = 0;
for(int i = 0; i < n; ++i){
result ^= A[i];
}
for(int i = 1; i < n; ++i){
result ^= i;
}
return result;
}
};