不修改数组找出数组中重复的数字

思路一

 // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        int[] assist = new int [length];
        for(int i = 0; i < length; i++){
            if(assist[numbers[i]] == 0){
                assist[numbers[i]] ++;
            }else{
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }

思路二

public class Duplicate1 {
    public static void main(String[] args){

        Duplicate1 duplicate1 = new Duplicate1();
        int[] arr = {2, 3, 5, 4, 3, 2, 6, 7};
        int len = arr.length;
        int res = duplicate1.getDupliation(arr, len);
        System.out.println(res);


    }

    /**
     * 统计数字在区间[start,end]范围内出现的次数
     * @param numbers
     * @param len
     * @param start
     * @param end
     * @return
     */
    public int countRange(int[] numbers,int len, int start,int end){
        if(len == 0 || numbers == null) return 0;

        int count = 0;
        for(int i = 0; i < len; i++){
            if(numbers[i] >= start && numbers[i] <= end){
                ++count;
            }

        }
        return count;
    }


    public int getDupliation(int[] numbers,int len){
        if(len == 0 ) return 0;

        int start = 1;
        int end = len - 1;
        while (end >= start){
            int middle = (start + end) >> 1;
            int count = countRange(numbers, len, 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;
    }
}

思路三

利用hashset的特性：不可重复，当添加集合中已有元素的时候，返回false

   public int getBySet(int[] numbers,int len){

        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < len; i++){
            boolean flg = set.add(numbers[i]);
            if(!flg)
                return numbers[i];
        }
        return  -1;
    }

思路四

该思路还可以用于求出所有的重复数字，只用筛选出map中value的值大于1的所有key就可以了

  public int getByHashMap(int[] numbers,int len){

        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < len; i++){
            if(map.get(numbers[i]) == null){
                int count = 0;
                map.put(numbers[i], ++count);
            }else {
                Integer valueCount = map.get(numbers[i]);
                valueCount++;
                map.put(numbers[i], valueCount);
            }
        }
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue() > 1)
                return entry.getKey();
        }
        return -1;
    }