劍指 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;

    }
}

優(yōu)秀答案

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;
        }