- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
借用 Map
题目要求我们找出数组中任意一个重复的数字，所以我们借助 Map 存储遍历过的数组，当遇到重复的数字时返回即可。
constfindRepeatNumber=function(nums){constmap=newMap()for(letiofnums){if(map.has(i))returnimap.set(i,true)}returnnull}
- 时间复杂度：O(n)
- 空间复杂度：O(n)
原地交换
如果没有重复的数字，遍历完后，元素 i 应该在下标为 i 的位置。
1.遍历数组，如果当前元素值与 i 不相等，则将该元素与下标 i 对应位置的元素交换，直到相等。
2.如果元素值与下标 i 对应位置的元素相等，则是重复的，返回该元素即可。
constfindRepeatNumber=function(nums){for(leti=0;i<nums.length;i++){while(nums[i]!=i){if(nums[i]===nums[nums[i]])returnnums[i]lettemp=nums[i]nums[i]=nums[temp]nums[temp]=temp}}returnnull}
- 时间复杂度：O(n)
- 空间复杂度：O(1)