题目一: 在一个长度为n的数组里的所有数字都在0 ~
n-1的范围内.数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次.请找出数组中任意一个重复的数字.例如,如果输入长度为7的数组{2,
3, 1, 0, 2, 5, 3},那么对应的数字是重复的数字2或3.
一,哈希表存储数字为key的对象,遍历数组,时间复杂度O(n), 空间复杂度O(n)
二,先对数组进行排序,然后一次比较与前一个是否相等, 时间复杂度, 空间复杂度根据排序类型不一样而有所不同
三,解析
如果这个数组中没有重复的数字,那么排序之后数字i
一定出现在下标为i
的位置上。
如果数组中有重复的数字,那么有的位置存在多个数字,有的位置可能没有数字。
var findDuplicateNum = (arr, n)=>{
if (!arr) return false
if (arr.length > n || arr.length === 0) return false
// 最大值 最小值的边界没有判断
for (let j = 0; j< arr.length; j++) {
if (arr[j] < 0 || arr[j] > n) {
return false
}
}
for (let i = 0; i < arr.length; i++) {
console.log('for current idx', i)
// let cur = arr[i]
while(arr[i] !== i) {
console.log(' while current idx', i)
if ( arr[ arr[i] ] === arr[i] ) {
// return arr[i]
console.log(arr[i])
return true
// break
}
var temp = arr[i]
// arr[i] = arr[arr[i]] 大BUG arr[i]已经变化了
// arr[arr[i]] = temp
arr[i] = arr[temp]
arr[temp] = temp
console.log(arr)
}
}
console.log('123')
return false
}
console.log(findDuplicateNum([2,3,1,0,2,5,3], 7))
此解法,时间复杂度O(n), 空间复杂O(1)
tip:尽管for循环里面有一个while循环,【但是每个数字最多交换两次就能找到自己的位置】