劍指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){//防止死循環(huán)

? ? ? ? ? ? return repeatNumberNotChangeArray(num,max,max);

? ? ? ? }else{

return repeatNumberNotChangeArray(num,mid,max);

? ? ? ? }

}

}