數組編程題01_劍指Offer03_數組中重復的數字

1 題目

在一個長度為n的數組里的所有數字都在0到n-1的范圍內。數組中某些數字是重復的，但不知道有幾個數字是重復的。也不知道每個數字重復幾次。請找出數組中任意一個重復的數字。例如，如果輸入長度為7的數組{2,3,1,0,2,5,3},那么對應的輸出是第一個重復的數字2。

2 嘗試解決

小弟不才，只想到暴力解決，通過兩次遍歷數組找出重復的內容，有就將數字放入duplication[0]并返回true，沒有就false，下面是代碼，方法上的注釋是牛客網給出的，方法內的是我自己寫的

public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    這里要特別注意~返回任意重復的一個，賦值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        //雙重循環遍歷數組
        for(int i=0;i<length;i++){
            for(int j=0;j<length;j++){
                //相同下標直接繼續
                if(i==j)
                    continue;
                //不同下標進行比較
                if(numbers[i]==numbers[j]){
                    //相等，即重復
                    duplication[0]=numbers[i];
                    return true;
                }
                //不相等則繼續運行，不做處理
            }
        }
        //循環結束后仍未停止運行，說明無重復
        return false;
    }
}

運行結果
在這里插入圖片描述

3 更進一步

雖然通過了測試，但暴力算法終究是不可取的，不妨看看他人的思路，學習學習。
雙重for循環的復雜度為O(n^2).

3.1 排序后比較

先排序后比較的復雜度為排序的O(nlogn)和一次遍歷O(n)，取大的為O(nlogn)，下面是代碼

public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    這里要特別注意~返回任意重復的一個，賦值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        //排序后比較
        //排序
        quickSort(numbers,0,length-1);
        //比較 最大為length-1防止越界
        for(int i=0;i<length-1;i++){
            if(numbers[i]==numbers[i+1]){
                duplication[0]=numbers[i];
                return true;
            }
        }
        //無重復
        return false;
        
    }
    
    public void quickSort(int arr[],int left,int right){
        if(right-left<=0)
            return;
        else{
            int pivot=arr[right];
            int partition=partitionIt(arr,left,right,pivot);
            quickSort(arr,left,partition-1);
            quickSort(arr,partition+1,right);
        }
        
    }
    public int partitionIt(int[]arr,int left,int right,int pivot){
        int leftPtr=left-1;
        int rightPtr=right;
        while(true){
            while(arr[++leftPtr]<pivot)
                ;
            while(rightPtr>0 && arr[--rightPtr]>pivot)
                ;
            if(leftPtr>=rightPtr)
                break;
            else
                swap(arr,leftPtr,rightPtr);
        }
        swap(arr,leftPtr,right);
        return leftPtr;
    }
    public void swap(int arr[],int index1,int index2){
        int temp=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }
}

運行結果
在這里插入圖片描述

3.2 哈希表

這種方法的想法就是在遍歷數組的過程中填充一個哈希表，每掃描到一個數字就查看哈希表中是否已有該數字，有就結束，沒有就返回。這種方法以O(n)的空間代價將時間效率提升至O(n)
但是在牛客的網頁上不允許導入包，所以下面貼一段eclipse中的代碼，以題目中的那個例子做測試。

	public static void main(String[] args) {
       int [] numbers= {2,3,1,0,2,5,3};
       int [] duplication=new int[1];
       duplicate(numbers, numbers.length, duplication);
       System.out.println(duplication[0]);
		
	}
	public static boolean duplicate(int numbers[],int length,int [] duplication) {
		 //哈希
        HashSet<Integer> set=new HashSet<>();
        for(int i=0;i<length;i++){
            //判斷是否已有
            if(set.contains(numbers[i])){
                //重復
                duplication[0]=numbers[i];
                return true;
            }else{
                //還沒有
                set.add(numbers[i]);
            }
        }
        //遍歷結束，無重復
        return false;
	}

運行結果
在這里插入圖片描述

3.3 結合題干分析

題目中所有數字都是在0到n-1之間，對數組進行排序，如果沒有重復的數字，那么排序后的數組下標和值應當是一一對應的，即 numbers[0]==0，numbers[1]==1，numbers[2]==2，以此類推，那么在對數組進行重排的過程中，假設當前掃描到了第 i 個位置，如果numbers[i]==i ,那么這個數字就處在正確的位置上，如果numbers[i]!=i，那么此時的number[i]就錯位了，假設此時number[i]==m，嘗試判斷 numbers[i]會不會等于numbers[m]，等于就說明重復了，不等于就應該將該數字放到正確的位置上，即把 i 和 m 上的數字進行交換，然后繼續向后判斷，直到找出重復的數字或結束重排。

public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    這里要特別注意~返回任意重復的一個，賦值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        //重排
        for(int i=0;i<length;i++){
            //判斷下標與當前值是否一一對應
            if(numbers[i]==i){
                //正確對應了，直接繼續
                continue;
            }else{
                //不一一對應
                //判斷i上的數字是否與numbers[i]上的數字相等
                //此處可將numbers[i]賦值給m，更易讀一些，而且可以防止numbers[i]被修改造成死循環
                int m=numbers[i];
                if(numbers[i]==numbers[m]){
                    //相等，重復了
                    duplication[0]=numbers[i];
                    return true;
                }else{
                    //不相等，交換兩者位置
                    int temp=numbers[i];
                    numbers[i]=numbers[m];
                    numbers[m]=numbers[i];
                }
            }
        }
        //重排結束，未重復
        return false;
    }
    
}

在這里插入圖片描述

3.4 與全解的代碼差異

全解的代碼

public boolean duplicate(int[] nums, int length, int[] duplication) {
    if (nums == null || length <= 0)
        return false;
    for (int i = 0; i < length; i++) {
        while (nums[i] != i) {
            if (nums[i] == nums[nums[i]]) {
                duplication[0] = nums[i];
                return true;
            }
            swap(nums, i, nums[i]);
        }
    }
    return false;
}

private void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}

可以看出他在一開始判斷了數組為空和長度未負數的情況，這是我所沒有考慮到的。
將swap方法抽出來單獨寫這一點我想到了，但是將swap方法設置成private我沒注意。
在for循環中直接判斷還是使用while這一點我倒是沒有注意，但是在leetcode中提交的時候使用if是無法通過的，只能用while，另外替換方法要注意，沒寫好會死循環的。

結語

一開始看書的時候看到下面的分析內容說要進行排序，但是對排序算法不熟悉，糾結了半天決定先按自己的想法試試再說，沒想到居然通過了，再一次驗證了一道問題有多種解法的，最重要的還是要思考。
排序和集合類方面仍有不足，劍指offer看累了就看點這方面的內容吧。

參考鏈接

1.快速排序—(面試碰到過好幾次)
2.時間復雜度大小比較
3.java各種集合類區別

本文鏈接：https://blog.csdn.net/xklx_z/article/details/108316481

智能推薦

【劍指offer】03.數組中重復的數字

題目描述 //03. 數組中重復的數字 // 找出數組中重復的數字。 // 在一個長度為 n 的數組 nums 里的所有數字都在 0～n-1 的范圍內。 // 數組中某些數字是重復的，但不知道有幾個數字重復了，也不知道每 // 個數字重復了幾次。請找出數組中任意一個重復的數字。排序法把數組排成升序，再遍歷找相鄰重復數集合法很粗暴，直接存hashset，存不進就是遇到重復了原地置換找重復...

劍指 Offer 03. 數組中重復的數字

解題思路： 1.遍歷數組中的元素，利用hashMap記錄數組元素的個數，其中key為數組元素，value為count，然后添加到map對象中 2.當count>1時，輸出key...

## 劍指offer 03——數組中重復的數字

題目均為leetcode上的題，這里是做刷題記錄。有自己的題解和大神們的題解，希望可以共同進步呀！原題連接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/ 描述：找出數組中重復的數字。在一個長度為 n 的數組 nums 里的所有數字都在 0～n-1 的范圍內。數組中某些數字是重復的，但不知道有幾個數字...