剑指 Offer 03. 数组中重复的数字

[Geekhyt]

原题链接

借用 Map

题目要求我们找出数组中任意一个重复的数字，所以我们借助 Map 存储遍历过的数组，当遇到重复的数字时返回即可。

const findRepeatNumber = function(nums) {
    const map = new Map()
    for (let i of nums) {
        if (map.has(i)) return i
        map.set(i, true)
    }
    return null
}

• 时间复杂度：O(n)
• 空间复杂度：O(n)

原地交换

如果没有重复的数字，遍历完后，元素 i 应该在下标为 i 的位置。

1.遍历数组，如果当前元素值与 i 不相等，则将该元素与下标 i 对应位置的元素交换，直到相等。
2.如果元素值与下标 i 对应位置的元素相等，则是重复的，返回该元素即可。

const findRepeatNumber = function(nums) {
  for (let i = 0; i < nums.length; i++) {
    while (nums[i] != i) {
      if (nums[i] === nums[nums[i]]) return nums[i]
      let temp = nums[i]
      nums[i] = nums[temp]
      nums[temp] = temp
    }
  }
  return null
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)