剑指offer3（java）

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

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

请找出数组中任意一个重复的数字(要求不改变原数组)。

解法： 对于数组中的数，根据鸽笼原理，n+1长度的数组中有n个数，这n个数在1~n内，那么一定存在重复度的数字。同理，在（n+1）/2长度的数组中，有(n+1)/2+1个数字，那么一定存在重复数字。这部分可以用递归实现。

public int repeatNumberNotChangeArray(int[] num,int min,int max){

if(min == max)return min;

    int count =0;

    int mid = (max + min) >>1;

    for(int i=0;i

if(num[i] <=mid && num[i]>= min)

count++;

    }

if(count > mid-min+1){

return repeatNumberNotChangeArray(num,min,mid);

    }else{

if(min == mid){//防止死循环

            return repeatNumberNotChangeArray(num,max,max);

        }else{

return repeatNumberNotChangeArray(num,mid,max);

        }

}

}