查找数组中至少一个重复的数字

1.一个数组长度是n+1 范围是1～n-1 查找至少一个数组中重复的数字

public static void main(String[] args) {
        //长度必须是N+1, 范围是1～N-1
        
        int[] a = new int[]{1,2,3,4,5,6,7,8,3,9};
        System.out.println(find1(a) + "");
        System.out.println(find2(a) + "");
    }
    
    static int find1(int[] a){
        int[] is = new int[a.length];
        for(int i = 0 ; i < a.length ; i++){
            is[a[i]] = ++is[a[i]];
            if(is[a[i]] > 1){
                return a[i];
            }
        }
        return -1;
    }
    
    static int find2(int[] a){
        int x = 0; 
        int y = 0;
        do{
            x = a[a[x]];
            y = a[y];
        }while(x != y);
        x = 0; //x y 获取到折中的位置
        do{
            x = a[x];
            y = a[y];
        }while(x != y);
        return x;
    }```

第一种方式使用位图当N较大的时候会比较费内存。
第二种方式使用单链表存在环来判断。虽然没第一种快，但是节省内存而且时间复杂度只为N，在特定条件下是一种比较实用的算法。