287. 寻找重复数

这道题太有技巧性了 首先 解题思路有两种 一种是二分查找 一种是快慢指针

• 二分查找
  1. 取n的中位数K 然后遍历nums
  2. 如果小于K的数量 大于等于K
  3. 那么表示 1-k中一定有重复的数 否则就在另一边 然后遍历
• 快慢指针
  1. 首先我们想办法把数组变成链表
  2. 如果存在重复数 那么表示一定是有环的
  3. 快慢指针(快指针速度2 慢指针速度1) 假设环周长C 除了环的距离M 移动了距离N 快慢指针相遇了
  4. 快慢指针相遇一定在环里 (2N - N)%C == 0 得到 N%C == 0
  5. 慢指针在环里进行的长度 N-M 一定是环的整数倍 (N-M)%C == 0
  6. 关键点就在这里 我们有公式 (N-M)%C == 0 N%M == 0 那么慢指针再走M步 一定会到达环入口
  7. 这道题还有一点很难想的就是 数组如何转换成链表 参考这个解题思路 题解

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)))
}