题目描述
https://leetcode.cn/problems/find-the-duplicate-number/description/
...
暴力方式可以使用两边遍历或者哈希表方式，但是根据题目要求空间复杂度需要为O(1)，因此需要采用其他方案。我们这里采用快慢指针的方式来实现。
使用快慢指针
题目中关键的提示点是【其数字都在1到n之间（包含1和n）】。
...
| Code Block | ||
|---|---|---|
| ||
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast){
slow = nums[slow];
fast = nums[nums[fast]];
}
int pre1 = 0;
int pre2 = slow;
while(pre1 != pre2){
pre1 = nums[pre1];
pre2 = nums[pre2];
}
return pre1;
}
} |
使用二分查找
| Code Block | ||
|---|---|---|
| ||
func findDuplicate(nums []int) int {
lo, hi := 1, len(nums)-1
for lo < hi {
mid := (lo + hi) >> 1
count := 0
for i := 0; i < len(nums); i++ {
if nums[i] <= mid {
count++
}
}
if count > mid {
hi = mid
} else {
lo = mid + 1
}
}
return lo
} |