剑指 Offer 03. 数组中重复的数字
2021-10-22 09:56:02

题目

剑指 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 的迭代顺序；特别是它不保证该顺序恒久不变。

还有其他的泛型见
https://hiszm.cnblogs.com/p/13755490.html

总结

我的答案其实修改一下就可以和第一个答案类似
通知对于有测试用例,最好加一个这个用来判断

if(nums==null||length==0){
            return false;
        }