/**

 * 找到数组中重复的数字

 * 问题描述：在长度为n的数组中，所有的元素都是0到n-1的范围内。

 * 数组中的某些数字是重复的，但不知道有几个重复的数字，也不知道重复了几次，请找出任意重复的数字。

 * 例如，输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出为2或3

 *

 */

public class DuplicateNumber {

    public static void main(String[] args) {

        int[] array = {2,3,1,0,2,5,3};

        int duplicate = duplicateNumber(array);

        System.out.println("重复的数字为: " + duplicate);

    }

    /**

     * 求数组中重复的数字

     * 分析：如果数组中没有重复的数字，则第i位置应该放置的数字为i。可以重排此数组，让对应位置上的数字对应。

     */

    private static int duplicateNumber(int[] array) {

        // TODO Auto-generated method stub

        if(array == null || array.length <= 0){

            return -1;

        }

        for(int i=0;i<array.length;i++){ //判断输入数组的合法性

            if(array[i] < 0 || array[i] >= array.length){

                return -1;

            }

        }

        for(int i=0;i<array.length;i++){

            if(i != array[i] && array[i] == array[array[i]]){ //重复数据

                return array[i];

            }

            while(i != array[i]){ //将数字与第m个位置上的数字交换

                exchange(array, i, array[i]);

            }

        }

        return -1;

    }

    /**

     * 交换数组array中的第i位和第j位

    public static void exchange(int[] array, int i, int j){

        int temp = array[i];

        array[i] = array[j];

        array[j] = temp;

    }

}