今天完成的事情：

1. 剑指offer 面试题3.2

明天计划的事情

1. 剑指offer 面试题4

2. 看基础

3. 代码还是不能落下，springboot学习1-2个小时

遇到的问题：

无

收获：

找出数组中重复的数字 

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。

现在的条件是 空间复杂度为O(1) ,所以需要用时间换空间。

/**
 * @description:  通过二分法查找重复数字,每次扫描都是统计全部数组中，符合范围的数字
 * 在8个位置上出现数字的范围为1-7，那么一定至少有一个数字有重复
 * 在值为 1-4 上 ，如果每个数字重复的次数超过4次，那重复的数字一定在1-4之间。要是在4次之内，就一定在5-7之间。
 * @param a
 * @return: java.util.Map
 * @author: Administrator
 * @date: 2018-03-24  下午 2:32
 */

public static Integer problem3_1(Integer[] a) throws Exception {
    //先判断数组是否为空
    if( a == null ||a.length == 0){
                throw new Exception("数组为空");
    }
       if( a == null ||a.length == 0){
               throw new Exception("数组为空");
    }
       for(int i= 0;i<a.length;i++){

           //判断这个数是否为空，为空就不进行比较
        if(a[i] == null ){
                          continue;
        }

                //判断这个数是否符合算法规则
      if(a[i] > a.length-1 || a[i]<1){
                       throw new Exception("数组创建异常");
        }
    }
   Integer start = 1;
    Integer end = a.length-1;
    while (end >= start){

           //获取中间大小的数值，例如1-7，4距离1有3位数，4-7有3位数，所以取4，而不是取数组位置上的中间位。
  Integer middle = (end+start)>>1;
    //统计 大小为start -- middle 之间的数字出现的次数
   int count =  count(a,start,middle);
        //当统计到 二分法 最右边的时候，即不断的二分直到只有一个数字的时候无法二分了
  if(end.equals(start)){
                  if (count>1){
                            return start;
       }
                  else {
                
         break;
       }
   }

               //count统计的数量大于每种数字假设只出现一次的数量，即假设1-4每个数字只出现一次，则本应只有4个数，但统计
     //1-4的数字却有5个，则对这些数字进行二分法后再次查找
     if(count>(middle-start + 1) ){
          end = middle;
      }
              //如果二分法的左边数字个数正常，那么重复的数字在左边一定有，右边也可能有，例如：1-4之间的数字没有1
        //而是有两个2.
        else {
          start = middle+1;
        }

     }

       return -1;
}


/**
 * @description:  统计整个数组中1-4之间的数字出现的次数
 * @param a
 * @param start
 * @param middle
 * @return: int
 * @author: Administrator
 * @date: 2018-03-24  下午 3:08
 */

private static int count(Integer[] a, Integer start, Integer middle){
       int count = 0;
    for( int i =0;i<a.length;i++ ){
              if( a[i]<= middle&&a[i]>=start ){
           count++;
        }
   }
       return count;
}