面试题3:数组中的重复数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。
思路一：排序，再查找

 public boolean duplicate(int numbers[],int length,int [] duplication) {
         if (numbers == null || length <= 0)   {return false;}
        if(duplication.length==0|| duplication==null) return false;
        Arrays.sort(numbers);
        for(int i=1,k=0;i<length;i++){
            if(numbers[i]==numbers[i-1])
            {duplication[k++]=numbers[i]; return true;}
        }
        return false;  
    }

思路二：用哈希表

   public boolean duplicate(int numbers[],int length,int [] duplication) {
         if (numbers == null || length <= 0)   {return false;}
         boolean[] hash = new boolean[length];
         // 初始化哈希表为false
        for (int i=0;i<length;i++)
            hash[i] = false;
        // 如果哈希表里没有这个数字，则加入，有则冲突
        for(int i=0;i<length;i++){
            int index = numbers[i];
            if(hash[index]==true)
            {
                duplication[0] = index;
                return true;
            }
            hash[index] = true;
        }
        return false;
    }

思路三：来回找，同时让每个数字归位

    public boolean duplicate(int numbers[],int length,int [] duplication) {
        // 这种方法的前提一定是数组中的数字小于length
        // 这个前提带来的便利是，如果没有重复数字，则排序之后一定是0-(n-1)
        // 即下标和值相等，如果存在不等的情况，则一定有重复
        if(numbers==null||length<=0) return false;
        
        for(int i=0;i<length;i++){
            // 为每个元素找到它应该在的位置i==numbers[i]
            while(i!=numbers[i]){
                // numbers[i]占了i的位置，如果numbers[i]自己位置上的值和自己相等，则重复
                if(numbers[numbers[i]]==numbers[i]){
                    duplication[0] = numbers[i];
                    return true;
                }
                //  否则交换，让numbers[i] 到自己的位置上去
                    int temp = numbers[numbers[i]];
                    numbers[numbers[i]] = numbers[i]; // 找到自己的位置
                    numbers[i] = temp; // i的位置可能还不对，继续找
                    
                
            }
        }
        return false;
    }

题目二：不修改数组找出重复的数字
长度为n+1,每个元素范围是1－n
思路：利用数组特征，对于数组中所有小于k 的数，如果个数超过k则重复数字一定在1-k当中，如果个数小于k，则重复数字在k+1－n当中。如果个数和k相等，则不能判断，一点一点减小k，直到不相等位置。

    public int getDuplication(int[] arr)
    {
        for(int i = 0;i < arr.length;i++)
        {
            if(arr[i] < 0 || arr[i] >= arr.length)
                throw new IllegalArgumentException("输入参数不合法");
        }
        int start = 0;
        int end = arr.length-1;
        int flag = 0;
        int middle = 0;
        while(end >= start)
        {
            if(flag == 0)
               middle = (end + start)/2;
            int count = countRange(arr,start,middle);
            if(end == start)
            {
                if(count > 1)
                    return start;
                else
                    break;
            }
            if(count > (middle-start+1))//说明(start,middle)这个区间有重复的数
            {
                end = middle;
                flag = 0;
            }else if(count == (middle-start+1))//不能判断(start,middle)这个区间有重复的数
            {
                middle = middle - 1;
                if(middle < start)//说明(start,middle)这个区间没有重复的数
                {
                    start = (start+end)/2 + 1;
                    flag = 0;
                }else
                    flag = 1;
            }else //说明(middle+1,end)这个区间有重复的数
            {
                start = middle + 1;
                flag = 0;
            }
        }
        return -1;
    }

    private int countRange(int[] arr, int start, int end)
    {
        int count = 0;
        for(int i = 0;i < arr.length;i++)
        {
            if(arr[i] >= start && arr[i] <= end)
                ++count;
        }
        return count;
    }