一、题目描述
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
二、思路分析：
这个问题有多种思路: 核心关键在于寻找到有相同的数值，找到一个就可以返回了
2.1 使用数组记录
时间复杂度O(n) 空间复杂度O(N)
var findRepeatNumber = function(nums) { const map = [] // 记录是否使用 for(const num of nums){ if(map[num]){ return num } map[num] = true } };
2.2 排序
通过给nums排序的方式，然后判断某个元素是否等于前一个元素，找到就可以返回了。 时间复杂度: O(NlogN) 这里sort排序底层就是快排或者归并排序了
var findRepeatNumber = function(nums) { nums.sort((a,b)=>a-b) for(let i=0;i<nums.length;i++){ if(i!=0&&nums[i]==nums[i-1])return nums[i] } };
2.3 哈希表+原地交换(最优解)
var findRepeatNumber = function(nums) { const obj = {} let cur for(let i=0;i<nums.length;i++){ cur = nums[i] if(obj[cur]){ return cur }else{ obj[cur] = true } } };
三种解决办法提交截图
四、总结：
- 第三种解法使用对象会比使用map更加快（毕竟map的实现思路就是通过key-value的形式） 本文剑指offer第一篇就到这里啦，欢迎👍
