数组中重复的数字

题目链接

• 牛客网

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围：0≤n≤10000

进阶：时间复杂度O(n) ，空间复杂度 O(n)

刷题思路

代码实现

/**
 * 方案一：将所有数据排序（升序或者降序都行），如果存在左右相等的情况就是重复了，输出一个即可；
 * 存在问题：时间复杂度依赖sort()函数
 */
function duplicateOne(numbers) {
  // 升序
  numbers = numbers.sort((a, b) => a - b)
  // 降序
  // numbers = numbers.sort((a, b) => b - a)

  for (let index = 0; index < numbers.length - 1; index++) {
    if (numbers[index] === numbers[index + 1]) {
      // 存在两个元素重复
      return numbers[index]
    }
  }
  return -1
}

/**
 * 方案二：借助空数组，循环遍历目标数组按照index的值放入 如果存在则重复
 */
function duplicateTwo(numbers) {
  const arr = []
  for (let i = 0; i < numbers.length; i++) {
    // 这部分依赖的是排序后，如果不重复理想情况下：numbers[index]===index的情况
    if (!arr[numbers[i]]) {
      arr[numbers[i]] = 1
    }
    else {
      // 存在则重复
      return numbers[i]
    }
  }
  return -1
}

/**
 * 方案三： 利用Set集合值唯一的特性
 */
function duplicateThree(numbers) {
  const set = new Set()
  for (const number of numbers) {
    if (set.has(number)) {
      return number
    }
    set.add(number)
  }
  return -1
}

console.log(duplicateOne([2, 3, 1, 0, 2, 5, 3]))
console.log(duplicateTwo([2, 3, 1, 0, 2, 5, 3]))
console.log(duplicateThree([2, 3, 1, 0, 2, 5, 3]))

一些建议