287. 寻找重复数
这道题太有技巧性了 首先 解题思路有两种 一种是二分查找 一种是快慢指针
- 二分查找
- 取n的中位数K 然后遍历nums
- 如果小于K的数量 大于等于K
- 那么表示 1-k中一定有重复的数 否则就在另一边 然后遍历
- 快慢指针
- 首先我们想办法把数组变成链表
- 如果存在重复数 那么表示一定是有环的
- 快慢指针(快指针速度2 慢指针速度1) 假设环周长C 除了环的距离M 移动了距离N 快慢指针相遇了
- 快慢指针相遇一定在环里 (2N - N)%C == 0 得到 N%C == 0
- 慢指针在环里进行的长度 N-M 一定是环的整数倍 (N-M)%C == 0
- 关键点就在这里 我们有公式 (N-M)%C == 0 N%M == 0 那么慢指针再走M步 一定会到达环入口
- 这道题还有一点很难想的就是 数组如何转换成链表 参考这个解题思路 题解
class FindDuplicate {
/*
*给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
*示例 1:
*
*输入: [1,3,4,2,2]
*输出: 2
*示例 2:
*
*输入: [3,1,3,4,2]
*输出: 3
*说明：
*
*不能更改原数组（假设数组是只读的）。
*只能使用额外的 O(1) 的空间。
*时间复杂度小于 O(n2) 。
*数组中只有一个重复的数字，但它可能不止重复出现一次。
* */
fun findDuplicate(nums: IntArray): Int {
var slow = nums[0]
var fast = nums[nums[0]]
while (slow != fast) {
slow = nums[slow]
fast = nums[nums[fast]]
}
var findle = 0
while (findle != slow) {
findle = nums[findle]
slow = nums[slow]
}
return slow
}
}
fun main() {
println(FindDuplicate().findDuplicate(intArrayOf(1, 3, 4, 2, 4)))
}
