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
参考资料: