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.
Example 1:
Input:[1,3,4,2,2]
Output: 2
Example 2:
Input: [3,1,3,4,2]
Output: 3
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.
这道题给了我们 n+1 个数，所有的数都在 [1, n] 区域内，首先让证明必定会有一个重复数，这不禁让博主想起了小学华罗庚奥数中的抽屉原理(又叫鸽巢原理)，即如果有十个苹果放到九个抽屉里，如果苹果全在抽屉里，则至少有一个抽屉里有两个苹果，这里就不证明了，直接来做题吧。题目要求不能改变原数组，即不能给原数组排序，又不能用多余空间，那么哈希表神马的也就不用考虑了，又说时间小于 O(n2)，也就不能用 brute force 的方法，那也就只能考虑用二分搜索法了，在区间 [1, n] 中搜索，首先求出中点 mid，然后遍历整个数组，统计所有小于等于 mid 的数的个数，如果个数小于等于 mid，则说明重复值在 [mid+1, n] 之间，反之，重复值应在 [1, mid-1] 之间，然后依次类推，直到搜索完成，此时的 low 就是我们要求的重复值，参见代码如下：
解法一：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = , right = nums.size();
while (left < right){
int mid = left + (right - left) / , cnt = ;
for (int num : nums) {
if (num <= mid) ++cnt;
}
if (cnt <= mid) left = mid + ;
else right = mid;
}
return right;
}
};
经过热心网友 waruzhi 的留言提醒还有一种 O(n) 的解法，并给了参考帖子，发现真是一种不错的解法，其核心思想快慢指针在之前的题目 Linked List Cycle II 中就有应用，这里应用的更加巧妙一些，由于题目限定了区间 [1,n]，所以可以巧妙的利用坐标和数值之间相互转换，而由于重复数字的存在，那么一定会形成环，用快慢指针可以找到环并确定环的起始位置，确实是太巧妙了！
解法二：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int slow = , fast = , t = ;
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;
}
};
这道题还有一种位操作 Bit Manipulation 的解法，也十分的巧妙。思路是遍历每一位，然后对于 32 位中的每一个位 bit，都遍历一遍从0到 n-1，将0到 n-1 中的每一个数都跟 bit 相 ‘与’，若大于0，则计数器 cnt1 自增1。同时0到 n-1 也可以当作 nums 数组的下标，从而让 nums 数组中的每个数字也跟 bit 相 ‘与’，若大于0，则计数器 cnt2 自增1。最后比较若 cnt2 大于 cnt1，则将 bit 加入结果 res 中。这是为啥呢，因为对于每一位，0到 n-1 中所有数字中该位上的1的个数应该是固定的，如果 nums 数组中所有数字中该位上1的个数多了，说明重复数字在该位上一定是1，这样我们把重复数字的所有为1的位都累加起来，就可以还原出了这个重复数字，参见代码如下：
解法三：
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int res = , n = nums.size();
for (int i = ; i < ; ++i) {
int bit = ( << i), cnt1 = , cnt2 = ;
for (int k = ; k < n; ++k) {
if ((k & bit) > ) ++cnt1;
if ((nums[k] & bit) > ) ++cnt2;
}
if (cnt2 > cnt1) res += bit;
}
return res;
}
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/287
类似题目：
Find All Numbers Disappeared in an Array
参考资料：
