剑指offer面试题3，找出数组中的重复数字(java实现)

给定一个长度为 n 的整数数组 num，数组中所有的数字都在 0∼n的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

解法：对于长度为n的数组，数字都在0~n之间。根据鸽笼原理，一定存在重复的数字。如果没有重复度的数字，将数组排序之后所有的数字都和它的下标是一致的。所以这里，我们可以将所有的数字放回到与它一致的下标中，如果在下标处已经存在改数字，那么久找到了重复的数字。

public class RepeatNumber {

    public static void main(String[] args){

        RepeatNumber rn =new RepeatNumber();

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

            System.out.println(rn.repeatNumber(num));

    }

    public int repeatNumber(int[] num){

        if(num.length==0)    return -1;

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

                   if(num[i] != i){

                        if(num[num[i]] == num[i]){

                            return num[i];

                        }else{

                            int tem = num[i];

                            num[i] = num[num[i]];

                            num[tem] = tem;

                        }

                    }

                      i++;

                }

            return -1;

        }

   }