劍指 Offer 03. 數(shù)組中重復(fù)的數(shù)字
2021-10-22 09:56:02

題目

劍指 Offer 03. 數(shù)組中重復(fù)的數(shù)字

在一個(gè)長(zhǎng)度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。

示例 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% 補(bǔ)充一點(diǎn)，題目給了數(shù)組值的范圍，所以不會(huì)越界！

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

另一個(gè)我們可以用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>();
這是一個(gè)泛型的寫法，表示 這個(gè)集合中只能保存 integer 類型的對(duì)象，其他對(duì)象無法保存，
取出時(shí) 也是直接是這個(gè)integer 對(duì)象

Set 接口也是 Collection 接口的子接口，它有一個(gè)很重要也是很常用的實(shí)現(xiàn)類——HashSet，Set 是元素?zé)o序并且不包含重復(fù)元素的 collection（List 可以重復(fù)），被稱為集。

HashSet 由哈希表（實(shí)際上是一個(gè) HashMap 實(shí)例）支持。它不保證 set 的迭代順序；特別是它不保證該順序恒久不變。

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

總結(jié)

我的答案其實(shí)修改一下就可以和第一個(gè)答案類似
通知對(duì)于有測(cè)試用例,最好加一個(gè)這個(gè)用來判斷

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