正文
[LeetCode] 287. Find the Duplicate Number（Floyd判圈算法）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
传送门
Description
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(n2
)
.
-
There is only one duplicate number in the array, but it could be repeated more than once.
思路
题意：
给定一个数组，包含n + 1个数，其数值在1-n之间，证明至少存在一个重复的数。假设仅有一个重复的数，找出它。
要求：
-
假设数组仅为可读，不允许改变数组
-
空间复杂度为O(1)，时间复杂度要求小于O(n
2
)
题解：
由于不允许改变数组，因此不能将数组排序，又因为额外的空间仅允许O(1)，因此，不考虑hash。复杂度不能为O(n
2
)，所以不能暴力求解。
方法一：为了降低复杂度，我们可以考虑二分，将复杂度降低为O（nlog
n
），每次二分，然后遍历数组，查看小于等于mid的数，如果个数小于等于mid，则证明重复的数小于等于mid，反之在[mid + 1,right]的区间。
方法二：此种方法利用floyd判圈算法的原理来求解，具体可以查看这里：click here
class Solution {
public:
//9ms
int findDuplicate(vector<int>& nums) {
if (nums.size() > ){
int slow = nums[],fast = nums[nums[]];
while (slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = ;
while (slow != fast){
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
return -;
}
//9ms
int findDuplicate(vector<int>& nums) {
int left = ,right = nums.size() - ;
while (left < right - ){
int mid = left + ((right - left) >> );
int cnt = ;
for (auto val : nums){
if (val <= mid) cnt++;
}
if (cnt <= mid) left = mid;
else right = mid;
}
return left;
}
};
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(n2
). - There is only one duplicate number in the array, but it could be repeated more than once.
题意： 给定一个数组，包含n + 1个数，其数值在1-n之间，证明至少存在一个重复的数。假设仅有一个重复的数，找出它。
要求：
- 假设数组仅为可读，不允许改变数组
- 空间复杂度为O(1)，时间复杂度要求小于O(n 2 )
题解： 由于不允许改变数组，因此不能将数组排序，又因为额外的空间仅允许O(1)，因此，不考虑hash。复杂度不能为O(n 2 )，所以不能暴力求解。
方法一：为了降低复杂度，我们可以考虑二分，将复杂度降低为O（nlog n ），每次二分，然后遍历数组，查看小于等于mid的数，如果个数小于等于mid，则证明重复的数小于等于mid，反之在[mid + 1,right]的区间。
方法二：此种方法利用floyd判圈算法的原理来求解，具体可以查看这里：click here
class Solution {
public:
//9ms
int findDuplicate(vector<int>& nums) {
if (nums.size() > ){
int slow = nums[],fast = nums[nums[]];
while (slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
fast = ;
while (slow != fast){
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
return -;
}
//9ms
int findDuplicate(vector<int>& nums) {
int left = ,right = nums.size() - ;
while (left < right - ){
int mid = left + ((right - left) >> );
int cnt = ;
for (auto val : nums){
if (val <= mid) cnt++;
}
if (cnt <= mid) left = mid;
else right = mid;
}
return left;
}
};
