Visits: 149

4 1 投票

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.

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(n^2)$.
There is only one duplicate number in the array, but it could be repeated more than once.

• 不能更改原数组（假设数组是只读的）
• 只能使用额外的 $O(1)$ 的空间
• 时间复杂度小于 $O(n^2)$
• 数组中只有一个重复的数字，但它可能不止重复出现一次

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]];
}
fast = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}

 while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}

while (fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) break;
}
4 1 投票

3条留言

（可选）如果您也有个人网站，不妨分享一下

3 评论

Hi Chrome 74.0.3729.108 Mac OS X 10_13_6

2019年6月19日 03:09

666 Chrome 85.0.4183.83 Windows 10

2020年10月21日 11:58

666