題目一：找出數(shù)組中重復的數(shù)字

題目描述

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

方法一

先將數(shù)組排序，從重復的數(shù)組中找出重復的數(shù)字就比較容易。排序一個長度為n的數(shù)組需要時間O(nlogn)的時間。

public static void method1(int[] array){
  int[] sortAray = quicklySort(array, 0, array.length - 1);
  for (int i = 0; i < sortAray.length-1; i++) {
    if (sortAray[i] == sortAray[i+1]){
      System.out.println("method1 "+sortAray[i]);
     }
   } 
}
public static int[] quicklySort(int[] arr, int left, int right){
        int l = left; // 左下標
        int r = right; // 右下標
        // pivot 中軸值
        int pivot = arr[(l + r)/2];
        int temp = 0; //臨時變量做交換時使用
        // while循環(huán)目的是讓比pivot值小的放到左邊
        // 比pivot值大的放到右邊
        while (l < r){
            // 在pivot的左邊一直找，找到大于等于pivot的值才退出
            while (arr[l] < pivot){
                l += 1;
            }
            // 在pivot的右邊一直找，找到小于等于pivot的值才退出
            while (arr[r] > pivot){
                r -= 1;
            }
            // 如果l >= r 說明pivot的左右兩的值，已經(jīng)按照左邊全部是
            // 小于等于pivot的值 右邊全部都是大于等于pivot的值
            if(l >= r){
                break;
            }
            // 交換
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            // 如果交換完后 發(fā)現(xiàn)arr[l] == pivot值 相等 r-- 前移
            if (arr[l] == pivot){
                r -= 1;
            }
            // 如果交換完后 發(fā)現(xiàn)arr[r] == pivot值 相等 l++ 后移
            if (arr[r] == pivot){
                l += 1;
            }
        }
        // 如果l==r 必須要l++ r-- 否則為出現(xiàn)棧溢出
        if(l == r){
            l += 1;
            r -= 1;
        }
        // 向左遞歸
        if (left < r){
            quicklySort(arr,left,r);
        }
        // 向右遞歸
        if(right > l){
            quicklySort(arr,l,right);
        }
        return arr;
    }

方法二

可以通過哈希表來解決這個問題。從頭到尾按順序掃描數(shù)組中的每個數(shù)字，每掃描到一個數(shù)字的時候，都可以用O(1)的時間來判斷哈希表是否已經(jīng)包含了該數(shù)字，如果還沒有這個數(shù)字，就把他加入哈希表。如果哈希表里面已經(jīng)存在該數(shù)字，就找到了一個重復的數(shù)字。時間復雜度為O(n)，但是空間復雜度為O(n)。

public static void method2(int[] array){
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (!map.containsValue(array[i])){
                map.put(i,array[i]);
            }else {
                System.out.println("method2 "+array[i]);
            }
        }
    }

方法三

從頭到尾依次掃描這個數(shù)組中的每個數(shù)字，當掃描到下表為i的數(shù)字時，首先比較這個數(shù)字用m表示是不是等于i。如果是，則接著掃描下一個數(shù)字；如果不是，則拿他再和第m個數(shù)字進行比較。如果他和第m個數(shù)字相等，就找到了一個重復的數(shù)字（該數(shù)字在下標i和m的位置都出現(xiàn)了）；如果他和第m個數(shù)字不等，就把第i個數(shù)字和第m個數(shù)字交換，把m放到屬于它的位置。

public static void method3(int[] array){
        if (array.length <= 0){
            return;
        }
        for (int i = 0; i < array.length; i++) {
            if (array[i]<0||array[i]>array.length-1){
                return;
            }
        }
        int m;
        int temp;
        for (int i = 0; i < array.length; i++) {
            m = array[i];
            while (m != i){
                if (m == array[m]){
                    System.out.println(m);
                    break;
                }
                temp = array[m];
                array[m] = array[i];
                array[i] = temp;
            }
        }
    }