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

题目一.找出数组中重复的数字

在一个长度为n的数组里所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3
思路：找到数组下标为m的数，如果下标m对应的值也是m，则跳过；如果值是n，则把下标m和下标n对应的值交换。如果交换的时候，发现两个对应的值相等，则为重复数字
解决方案：

public static boolean duplicate(int numbers[], int length, int[] duplication){
        if (numbers == null || length <=0){
            return false;
        }

        for (int i=0; i<length; i++){
            if (numbers[i] < 0 || numbers[i] > length-1){
                return false;
            }
        }

        for (int i=0; i<length; i++){
            while (numbers[i] != i){
                if (numbers[i] == numbers[numbers[i]]){
                    duplication[0] = numbers[i];
                    return true;
                }

                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
        return false;
    }

题目二：不修改数组找出重复的数字

在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3.
思路：把数字从中间的数字m分为两部分，前面一半为1_{m，后面一半为m+1}n，如果1~m的数字的数目超过m，则这个区间段一定有重复数字然后再依次递归找到重复数字。
解决方案：

public static int getDuplication(int[] numbers, int length){
        if (numbers == null || length <= 0) return -1;
        int start = 1;
        int end = length - 1;
        while (end > start){
            int middle = ((end - start)>>1)+start;
            int count = countRange(numbers, length, start, middle);
            if (end == start){
                if (count > 1) return start;
                else break;
            }
            if (count > (middle - start +1)) end = middle;
            else start = middle + 1;
        }
        return -1;
    }

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