Skip to main content

数组中重复的数字

题目​

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

示例

输入: [2, 3, 1, 0, 2, 5, 3]

输出: 2 或 3

题解​

很容易想到的就是哈希表, 不过这会导致空间复杂度变为 O(N).

我们注意到题目在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内, 那意味着如果没有重复数字, 在从小到大排序后, 一定会索引值 i 和 nums[i] 相等. 比如 [3, 0, 1, 2] 排序后变成 [0, 1, 2, 3].

因为数组中有重复数字, 所以在排序后, 某个重复数字 num 一定在 nums[num] 的位置, 也一定会占据在其他索引 i 的位置上, 因此在只要找到 nums[nums[i]] === nums[i], 也就找到了那个重复数字.

以 [2, 3, 1, 0, 2, 5, 3] 为例:

  • 第一个数字 2 不等于索引 0, 因此需要和 nums[2] 交换, 变成 [1, 3, 2, 0, 2, 5, 3]
  • 第一个数字 1 不等于索引 0, 因此需要和 nums[1] 交换, 变成 [3, 1, 2, 0, 2, 5, 3]
  • 第一个数字 3 不等于索引 0, 因此需要和 nums[3] 交换, 变成 [0, 1, 2, 3, 2, 5, 3]
  • 第一个数字 0 等于索引 0, 第二个数字 1 等于索引 1, 第三个数字 2 等于索引 2, 第四个数字 3 等于索引 3
  • 第四个数字 2 不等于索引 4, 但此时它和 nums[2] 相等了, 也就找到了那个重复的数字
/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function (nums) {
  const n = nums.length

  for (let i = 0; i < n; i++) {
    while (nums[i] !== i) {
      if (nums[nums[i]] === nums[i]) {
        return nums[i]
      } else {
        let tmp = nums[i]
        nums[i] = nums[tmp]
        nums[tmp] = tmp
      }
    }
  }
}

复杂度分析​

时间复杂度: O(N)

空间复杂度: O(1)