剑指Offer-Javascript版-找出数组中的数字

对应LeetCode上的题目：面试题03. 数组中重复的数字

题目描述：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字

题目描述

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字

解法一，暴力求解法

先把输入的数字排序，从排序的数字中找出重复的数字，即需要从头到尾扫描排序后的数组就可以了，排序一个长度为 n 的数组需要 O(nlogn) 的时间（排序最快的速度是 O(nlogn) ，即快速排序）

1
2
3
4
5
6
7
8
9
10
11

const findRepeatNumber = (nums) => {
  // 先排序
  nums.sort((a, b) => a - b)

  for(let i = 0, len = nums.length; i < len-1; i++) {
    // 比较前后的值是否相同
    if(nums[i] === nums[i+1]) {
      return nums[i]
    }
  }
}

可想而知，这种解法并不是那么令人满意，因为需要先把数组排序

解法二，使用对象

使用对象来解决这个问题，从头到尾遍历整个数组，依次把数组的每一项当作对象的 key 值存进对象。如果数组的某个项在对象中存在，那么我们就可以认为这个值在数组中重复了，直接返回即可

1
2
3
4
5
6
7
8
9
10
11
12
13

const findRepeatNumber = (nums) => {
  // 用来存放是否遍历过的数组的项
  const obj = {}
  for(let i = 0; i < nums.length; i++) {
    // 数组的项是否已经是对象obj的键值了
    if(obj[nums[i]]) {
      return nums[i]
    } else {
      obj[nums[i]] = 1
    }
  }
}

解法三，数学分析法

从头到尾遍历数组

• 当数组下标为 i 的时候，比较这个数字（用 m 表示）是不是等于 i，如果是，则接着扫描下一个数字。

• 如果不是，拿它与第 m 个数字进行比较。如果它和第 m 个数字相等，就找到了一个重复的数组（i 和 m 的位置上都存在数字 m）。如果它和第 m 个数字不相等，就把第 i 个位置上的数字和第 m 个位置上的数字交换，那么 第 m 位上的数字就是 m 了

• 重复这个比较，直到发现一个重复的数字

[2, 3, 1, 0, 2, 5, 3] 举个例子：

• 首先遍历这个数组，从 0 位置上开始遍历。0 上面的数字是 2，那么我们可以直接拿数字 2 和 2 位置上的 1 做比较，结果不相等，交换位置。交换之后的数组是 [1, 3, 2, 0, 2, 5, 3]

• 此时 0 位置上面的数字是 1，仍然不相等，继续和下标为 1 的 数字 3 做交换。交换之后的数组是 [3, 1, 2, 0, 2, 5, 3]

• 此时 0 位置上面的数字是 3，仍然不相等，继续和下标为 3 的 数字 0 做交换。交换之后的数组是 [0, 1, 2, 3, 2, 5, 3]

• 这时候 0 位置上的数字是 0 了，那么我们可以直接遍历下一个数字了，可知接下来的数字 1，2，3 都与坐标相等，不用进行交换操作。

• 接下来到位置 4 的数字 2 ，由于数字与位置不相等，再比较位置 2 上的数字。发现位置 2 上的数字也是 2 了，因此我们便找到了一个重复的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

      // 交换数组两个位置上的项，这里是i 和 num[i] 交换
      let temp= nums[i]
      nums[i] = nums[temp]
      nums[temp] = temp
    }
  }
}