Skip to main content

3-10 287.寻找重复数

Date：2022-03-13 16:18:46

标签：

  • 二分法
  • 快慢指针

题目：287.寻找重复数 ( 中等😕 )​

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

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

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

示例​

示例 1

输入：nums = [1,3,4,2,2]
输出：2

示例 2

输入：nums = [3,1,3,4,2]
输出：3

分析​

以下方法空间复杂度都是 O(n)，满足题目要求

  • 暴力法

    双层 for 循环，按个按个比较，如果相等 即找到该元素

    • 时间复杂度 O(n^2)

  • 二分法

    根据这个图的思路，然后在纸上画一画，就明白了

    image-20220310090759661

    • 这个题目条件很苛刻：其数字都在 [1, n] 范围内（包括 1 和 n），而且只有 一个重复的整数

      所以才可以这样操作，下面的快慢指针也是如此

    • 时间复杂度 O(n*logn)

  • 快慢指针

    建议参考：二分法&快慢指针

    • 时间复杂度 O(n)

题解​

二分法

function findDuplicate(nums: number[]): number {
  const len = nums.length
  let l = 0,
    r = len - 1,
    ans = -1

  while (l <= r) {
    const mid = Math.floor((r + l) / 2)

    let cnt = 0
    for (let i = 0; i < len; ++i) {
      if (nums[i] <= mid) {
        ++cnt
      }
    }

    console.log('[]:', r, mid, l, cnt)
    if (cnt <= mid) {
      l = mid + 1
    } else {
      r = mid - 1
      ans = mid
    }
  }

  return ans
}

快慢指针

function findDuplicate111(nums: number[]): number {
  let slow = 0,
    fast = 0

  // Find the entrance to the ring
  while (true) {
    slow = nums[slow]
    fast = nums[nums[fast]]

    if (fast == slow) {
      break
    }
  }

  // Find the element, based on the entry
  let find = 0
  while (true) {
    find = nums[find]
    slow = nums[slow]
    if (find == slow) {
      break
    }
  }

  return find
}

扩展 1：141. 环形链表 ( 简单😄 )

扩展 2：142. 环形链表 II ( 中等😕 )