Give an array contains n+1 number which range from 1 to n. Find the duplicates.
e.g. 1, 2, 3, 3 -> 3
1, 3, 2, 4, 3 -> 3
Requirements
Space o(1)
Time o(n)
Since there are 1..n number in n+1 size array, every number can link to other using the form num -> array[num].
Note if there are duplicates amount 1 to n, then there will be different numbers links to the same number.
For example: 1->3->4->3 which forms a loop, now the problem becomes finding the starting of loop.
which can be done by https://en.wikipedia.org/wiki/Cycle_detection
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[nums[0]];
while(slow!=fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
slow = 0;
while(slow!=fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
No comments:
Post a Comment