# 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.

Example 1:

``````Input: [1,3,4,2,2]
Output: 2
``````

Example 2:

``````Input: [3,1,3,4,2]
Output: 3
``````

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant,  O (1) extra space.
3. Your runtime complexity should be less than  O ( n 2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

``````class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = 1, right = nums.size();
while (left < right){
int mid = left + (right - left) / 2, cnt = 0;
for (int num : nums) {
if (num <= mid) ++cnt;
}
if (cnt <= mid) left = mid + 1;
else right = mid;
}
return right;
}
};
``````

``````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(vector<int>& nums) {
int res = 0, n = nums.size();
for (int i = 0; i < 32; ++i) {
int bit = (1 << i), cnt1 = 0, cnt2 = 0;
for (int k = 0; k < n; ++k) {
if ((k & bit) > 0) ++cnt1;
if ((nums[k] & bit) > 0) ++cnt2;
}
if (cnt2 > cnt1) res += bit;
}
return res;
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/287

First Missing Positive

Missing Number

Single Number

Find All Numbers Disappeared in an Array

Set Mismatch

Array Nesting

Linked List Cycle II

https://leetcode.com/problems/find-the-duplicate-number/

https://leetcode.com/problems/find-the-duplicate-number/discuss/72872/O(32*N)-solution-using-bit-manipulation-in-10-lines

https://leetcode.com/problems/find-the-duplicate-number/discuss/73045/Simple-C%2B%2B-code-with-O(1)-space-and-O(nlogn)-time-complexity

https://leetcode.com/problems/find-the-duplicate-number/discuss/72846/My-easy-understood-solution-with-O(n)-time-and-O(1)-space-without-modifying-the-array.-With-clear-explanation.

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation