题目
剑指 Offer 03. 数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
我的答案
class Solution { public int findRepeatNumber(int[] nums) { int x=-1; int [] p =new int[100000]; for(int i=0;i<p.length-1;i++){ p[i]=-1; } for(int i=0;i<=nums.length-1;i++){ if(p[nums[i]]==-1){ p[nums[i]]=0; }else{ p[nums[i]]++; } } for(int i=0;i<p.length-1;i++){ if(p[i]>0){ x=i; break; } } //System.out.println(Arrays.toString(nums)); return x; } }
优秀答案
Java 2ms 100% 补充一点，题目给了数组值的范围，所以不会越界！
class Solution { public int findRepeatNumber(int[] nums) { int[] arr = new int[nums.length]; for(int i = 0; i < nums.length; i++){ arr[nums[i]]++; if(arr[nums[i]] > 1) return nums[i]; } return -1; } }
另一个我们可以用hash来做
class Solution { public int findRepeatNumber(int[] nums) { Set<Integer> set= new HashSet<Integer>(); int res=-1; for(int i:nums) { if(!set.add(i)){ res=i; break; } } return res; } }
Set<Integer> set= new HashSet<Integer>();
这是一个泛型的写法，表示 这个集合中只能保存 integer 类型的对象，其他对象无法保存，
取出时 也是直接是这个integer 对象
Set 接口也是 Collection 接口的子接口，它有一个很重要也是很常用的实现类——HashSet，Set 是元素无序并且不包含重复元素的 collection（List 可以重复），被称为集。 HashSet 由哈希表（实际上是一个 HashMap 实例）支持。它不保证 set 的迭代顺序；特别是它不保证该顺序恒久不变。