Given an arraynums
containingn + 1
integers where each integer is between1
andn
(inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Notice
- 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(n^2).
- There is only one duplicate number in the array, but it could be repeated more than once.
Have you met this question in a real interview?
Yes
Example
Givennums
=[5,5,4,3,2,1]
return5
Givennums
=[5,4,4,3,2,1]
return4
class Solution {
public:
/\*\*
\* @param nums an array containing n + 1 integers which is between 1 and n
\* @return the duplicate one
\*/
int findDuplicate\(vector<int>& nums\) {
// Write your code here
if \(nums.empty\(\)\) {
return -1;
}
int slow = 0, fast = 0;
slow = nums\[slow\];
fast = nums\[nums\[fast\]\];
while \(slow != fast\) {
slow = nums\[slow\];
fast = nums\[nums\[fast\]\];
}
fast = 0;
while \(slow != fast\) {
slow = nums\[slow\];
fast = nums\[fast\];
}
return slow;
}
};