0287. Find the Duplicate Number
https://leetcode.com/problems/find-the-duplicate-number
Description
Given an array of integers nums
containing n + 1
integers where each integer is in the range [1, n]
inclusive.
There is only one repeated number in nums
, return this repeated number.
You must solve the problem without modifying the array nums
and uses only constant extra space.
Example 1:
**Input:** nums = [1,3,4,2,2]
**Output:** 2
Example 2:
**Input:** nums = [3,1,3,4,2]
**Output:** 3
Example 3:
**Input:** nums = [1,1]
**Output:** 1
Example 4:
**Input:** nums = [1,1,2]
**Output:** 1
Constraints:
1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
All the integers in
nums
appear only once except for precisely one integer which appears two or more times.
Follow up:
How can we prove that at least one duplicate number must exist in
nums
?Can you solve the problem in linear runtime complexity?
ac
class Solution {
public int findDuplicate(int[] nums) {
// fast/slow pointers
int fast = nums[0], slow = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
}while (fast != slow);
int i = nums[0];
while (i != slow) {
i = nums[i];
slow = nums[slow];
}
return i;
}
}
Last updated
Was this helpful?