Skip to main content

寻找重复数

题目​

给定一个包含 n + 1 个整数的数组 nums, 其数字都在 [1, n] 范围内(包括 1 和 n), 可知至少存在一个重复的整数.

假设 nums 只有一个重复的整数, 返回这个重复的数.

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间.

提示:
  • 1 <= n <= 10⁵
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中 只有一个整数出现两次或多次, 其余整数均只出现一次
进阶:
  • 如何证明 nums 中至少存在一个重复的数字?
  • 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗?
示例
输入: nums = [1,3,4,2,2]
输出: 2
输入: nums = [3,1,3,4,2]
输出: 3
输入: nums = [3,3,3,3,3]
输出: 3

题解​

  • 将数组看作链表:

    • 数组的索引 i 可以看作链表的节点.
    • nums[i] 可以看作节点 i 指向的下一个节点.
    • 由于存在重复数字, 因此链表中必然存在环.

  • 使用快慢指针找到环的入口:

    • 定义两个指针 slow 和 fast, 初始时都指向数组的第一个元素 nums[0].
    • slow 指针每次移动一步, fast 指针每次移动两步.
    • 当 slow 和 fast 指针相遇时, 说明找到了环中的一个节点.
    • 然后将 slow 指针重新指向数组的第一个元素 nums[0], fast 指针保持不变.
    • 两个指针同时移动, 每次都移动一步, 直到它们再次相遇.
    • 此时 slow 指针指向的元素就是环的入口, 即为重复的数字.

代码首先初始化 slow 和 fast 指针, 然后使用 while 循环找到环中的一个节点. 然后将 slow 指针重新指向数组的第一个元素, 再次使用 while 循环找到环的入口. 最后返回 slow 指针指向的元素, 即为重复的数字.

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function (nums) {
  let slow = nums[0]
  let fast = nums[nums[0]]
  while (slow !== fast) {
    slow = nums[slow]
    fast = nums[nums[fast]]
  }
  slow = 0
  while (slow !== fast) {
    slow = nums[slow]
    fast = nums[fast]
  }
  return slow
}