Skip to main content

287. Find the Duplicate Number

分析

这道题二分的思路挺难想的 (二分查找除了对索引二分,还有值域二分)
体会 count 数量 与 mid 之间的关系

利用环的方法更难想 QAQ 「这辈子是不可能了👀」

用 [1,2,2,3] 作为例子
nums[1] = 2 1 -> 2
nums[2] = 2 2 -> 2
1 -> 2 -> 2

用 nums[p] 拿到的是 nums 的 next

btw...

参考

题解

二分

const findDuplicate = (nums) => {
let low = 1
let high = nums.length - 1
while (low < high) {
const mid = (low + high) >> 1
let count = 0
for (let i = 0; i < nums.length; i++) {
if (nums[i] <= mid) {
count++
}
}
if (count > mid) {
high = mid
} else {
low = mid + 1
}
}
return low
}

const findDuplicate = (nums) => {
let slow = nums[0], fast = nums[0]

while (slow && fast) {
slow = nums[slow]
fast = nums[nums[fast]]

if (slow === fast) {
fast = nums[0]

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