【Q3】剑指Offer面试题三的题目二：在不修改原数组的情况下找出重复的数字

【Q3】剑指Offer面试题三的题目二：在不修改原数组的情况下找出重复的数字

题目：在不修改原数组的情况下找出重复的数字。
在一个长度为n+1的数组里的所有数字都在1~n范围内，所有数组至少有一个数组是重复的。请找出任意一个重复得数字。但不能修改原数组。如测试用例：
{2, 3, 5, 4, 3, 2, 6, 7}，对应的重复数字但是2或者3.

public class Q2 {
    public static void main(String[] args) {
        int[] test = {2, 3, 5, 4, 3, 2, 6, 7};
        //排序再比较输出的方法
        //另外再耗用一定的空间N，复制进行比较
        辅助数组

        HashSet duplicateNumber = new HashSet<>();
        int[] auxilily = new int[8];
        for (int i = 0; i < test.length; i++) {
            int temp = test[i];
            if (auxilily[temp] == 0) {
                auxilily[temp]++;
            }else{
                duplicateNumber.add(temp);
            }
        }
        System.out.println(duplicateNumber);
    }
}

二分查找算法：

import java.util.HashSet;

public class Q2 {
    public static void main(String[] args) {
        int[] test = {2, 3, 5, 4, 3, 2, 6, 7};
        //排序再比较输出的方法
        //另外再耗用一定的空间N，复制进行比较
        辅助数组
        int N = test.length;
        int num = getDuplicate(test);
        System.out.println(num);
    }

    public static int getDuplicate(int[] arr) {
        int start = 1, end = arr.length - 1;
        while (start <= end) {
            int mid = (end - start) / 2 + start;
            int count = getCount(arr, start, mid);
            if (start == end) {
                if (count > 1) {
                    return start;
                } else {
                    break;
                }
            }
            if (count > (mid - start + 1)) {
                //说明有重复元素
                end = mid;
            } else {
                //相反
                //因为 数组中肯定有重复的元素，不上一半就在这
                start = mid + 1;
            }
        }
        return -1;
    }

    private static int getCount(int[] arr, int start, int end) {
        if (arr == null) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= start && arr[i] <= end) {
                count++;
            }
        }
        return count;
    }
    public static void  auxiliary(int[] test){
        HashSet duplicateNumber = new HashSet<>();
        int[] auxilily = new int[8];
        for (int i = 0; i < test.length; i++) {
            int temp = test[i];
            if (auxilily[temp] == 0) {
                auxilily[temp]++;
            }else{
                duplicateNumber.add(temp);
            }
        }
        System.out.println(duplicateNumber);
    }
}

参考来源：
https://www.cnblogs.com/aiguozou/p/11438001.html