数组 找出重复的数字（不修改数组）
题目：
- 在一个长度为n+1的数组中所有数组都在1~n 的范围内，所以数中至少有一数字是重复的；请找出数组中任意一个重复的数字，但不能修改原数组；
例如：
- 输入长度为8（n+1）的数组{2，3，5，4，3，2，6，7}，那么对应的输出重复的数字是2或3；
分析：
- 假如没有重复的数字，那么在1~n（1~7）的范围内就只会有n(7)个数字；由于数组包含超过n(7)个数字，所以一定包含了重复的数字；
- 我们从1~n（7）的数字从中间的数字m（4）分为两部分，前面一半为1~m（1~4），后面的一半为m+1~n（5~7）；如果1~m（4）的数字超过m（4），那么重复的数字一定在这里面；
- 意思就是：如果1~4的这个范围的数，在数组的中个数超过了4，那么就一定有重复的数；
- 否则，另一半里面，一定包含重复的数字；
- 然后我们可以继续把包含重复的区间一分为二，直到找到一个重复的数字；
- 这个过程类似二分查找；
A3.java
package No2_Array;
import java.util.Arrays;
public class A3 {
public void duplicate(int []a,int []num){
if(a.length<=0||a==null){
return ;
}
A3 a3 = new A3();
int k = 0;
int left = 1;
int right = a.length-1;
//当相等的时候，就是一个数，如果这个数的count大于1，则是重复数字
while(left <= right){
int mid = (left+right)>>1;//mid = 4，相当于/2
//不是递归调用，先比较左边的（这个左边的一段数，不是数组左边的数字，而是从从小到大，左半边的数），如果左边的数字大于该段数字的范围，就包含重复的数字
int count = a3.check(a, left, mid);
//直到最后才会剩下一个数字，判断最后的这一个数的个数是否大于1
if(left == right){
if(count > 1){//判断的仅剩最后一个元素，而且出现的次数还大于1，那就是重复的元素了
num[k++] = left;//放到数组里面
break;
}
else{
break;//如果没有找到元素，也退出
}
}
不是最后一个数，就一直判断二分
//这个是比较前一半
if(count > (mid-left+1)){//代表这里面有重复，然后缩小范围继续拆分
right = mid;
}
//这个是比较后一半
else{
//没有重复
left = mid+1;
}
}
}
//找每一段在该范围内[p，q]的个数
public int check(int num[],int p,int q){
if(num == null){
return 0;
}
//比较某一段的数字，出现在整个数组中的次数，如果大于该段数字的范围，就是含重复的数
int sum = 0;
for(int i = 0;i < num.length;i++){
if(num[i] >= p && num[i] <= q){
sum++;
}
}
return sum;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[] = new int[]{2,3,1,4,0,3,2};
//用于存重复的数
int []num = new int[a.length];
new A3().duplicate(a,num);
//还有一种方法打印，不需要用for循环
System.out.println(Arrays.toString(num));
}
}