本系列導航：劍指offer（第二版）java實現(xiàn)導航帖

面試題3：數(shù)組中重復的數(shù)

題目要求：
在一個長度為n的數(shù)組中，所有數(shù)字的取值范圍都在[0,n-1]，但不知道有幾個數(shù)字重復或重復幾次，找出其中任意一個重復的數(shù)字。

解法比較：

package chapter2;
/**
 * Created by ryder on 2017/6/11.
 * 一個長度為n的數(shù)組，值的范圍在0~n-1內(nèi)，有一個或多個數(shù)字重復，求其中任意一個
 */
public class P39_DuplicationInArray {
    //方法一：暴力求解，不會修改原始數(shù)據(jù)，時間復雜度o(n^2)，空間復雜度o(1)
    public static int getDuplication(int[] data){
        if(data==null || data.length<2)
            return -1;
        for(int i=0;i<data.length-1;i++){
            for(int j=i+1;j<data.length;j++){
                if(data[i]==data[j])
                    return data[i];
            }
        }
        return -1;
    }
    //方法二：排序，會修改原始數(shù)據(jù)，時間復雜度o(nlogn)，空間復雜度o(1)
    public static int getDuplication2(int[] data){
        if(data==null || data.length<2)
            return -1;
        //Arrays.sort(data); //或者使用內(nèi)置函數(shù)進行排序
        quickSort(data,0,data.length-1);
        if(data.length<2)
            return -1;
        int prev = data[0];
        for(int i=1;i<data.length;i++){
            if(data[i]==prev)
                return prev;
            else
                prev = data[i];
        }
        return -1;
    }
    public static void quickSort(int[] data,int start,int end){
        if(start>=end)
            return;
        int bound = partion(data,start,end);
        quickSort(data,start,bound-1);
        quickSort(data,bound+1,end);
    }
    public static int partion(int[] data,int start,int end){
        if(start>=end)
            return end;
        int pivot = data[start];
        int left = start, right = end;
        while(left<right){
            while(left<right && data[right]>=pivot)
                right--;
            if(left<right)
                data[left++] = data[right];
            while(left<right && data[left]<pivot)
                left++;
            if(left<right)
                data[right--] = data[left];
        }
        data[left] = pivot;
        return left;
    }

    //方法三：借助哈希表，不會修改原始數(shù)據(jù)，時間復雜度o(n),空間復雜度o(n)
    public static int getDuplication3(int[] data){
        if(data==null || data.length<2)
            return -1;
        int[] hashTable = new int[data.length];
        for(int item:data){
            if(hashTable[item]>=1)
                return item;
            else{
                hashTable[item] = 1;
            }
        }
        return -1;
    }

    //方法四：根據(jù)數(shù)字特點排序，會修改原始數(shù)據(jù)，時間復雜度o(n),空間復雜度o(1)
    public static int getDuplication4(int[] data){
        if(data==null || data.length<2)
            return -1;
        for(int i=0;i<data.length;i++){
            while(data[i]!=i){
                if(data[i]==data[data[i]])
                    return data[i];
                else{
                    int temp = data[i];
                    data[i] = data[temp];
                    data[temp] = temp;
                }
            }
        }
        return -1;
    }

    //方法五：類似于二路歸并，這個思路應該說是二路計數(shù)，不修改原始數(shù)據(jù)，時間復雜度o(nlogn),空間復雜度o(1)
    public static int getDuplication5(int[] data){
        if(data==null || data.length<2)
            return -1;
        //數(shù)組值在[start,end]間
        int start = 0;
        int end = data.length-2;
        while(start<=end){
            int middle = (end-start)/2+start;
            int count = countRange(data,start,middle);
            if(start==end){
                if(count>1)
                    return start;
                else
                    return -1;
            }
            if(count>middle-start+1)
                end = middle;
            else
                start = middle+1;
        }
        return -1;
    }
    public static int countRange(int[] data,int start,int end){
        int count = 0;
        for(int i=0;i<data.length;i++){
            if(start<=data[i] && end>=data[i])
                count++;
        }
        return count;
    }
    public static void main(String[] args){
        int[] data = {2,3,1,0,2,5,3};
        System.out.println(getDuplication(data));
        System.out.println(getDuplication2(data));
        System.out.println(getDuplication3(data));
        System.out.println(getDuplication4(data));
        System.out.println(getDuplication5(data));

        int[] data1 = {2,3,1,0,4,5,5};
        System.out.println(getDuplication(data1));
        System.out.println(getDuplication2(data1));
        System.out.println(getDuplication3(data1));
        System.out.println(getDuplication4(data1));
        System.out.println(getDuplication5(data1));
    }
}

運行結(jié)果(前面幾個方法會更改原數(shù)組，但不影響測試功能)

2
2
2
2
2
5
5
5
5
5