今天完成的事情：

1. 剑指offer 面试题3

明天计划的事情

1. 剑指offer 面试题3

2. 看基础

遇到的问题：

无

收获：

找出数组中重复的数字 

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

解决思路：类似于哈希表的算法

把数字集合看成数组，看下标为k(k = 0,1,2,3...)数字 i 在其以数字的值为下标 a[i] 处的值是否相等  a[i] == i  不相等就交换数值, a[ k ] <--> a[ a[k] ]  ,如果再次碰到相同的值就可以去相应的下标处看是否有重复的值

实现代码：

    public static Map problem3(Integer[] a) throws Exception {

       LinkedHashMap<Integer,Integer> number = new LinkedHashMap<Integer, Integer>();

        //先判断数组是否为空
      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]<0){
                           throw new Exception("数组创建异常");
        }

                   //当 数值 和 a[数值]  不等时
      while(i != a[i] ){

                             //判断 下标为a[数值] 是否为空, 为空直接交换
         if(a[a[i]] == null){
                   a[a[i]] = a[i];
                    a[i] = null;
                    break;
                    //例如：看 a[3](假设为7) 和a[ a[3] ] 的值否相等， 如果相同的话，标记一下。
          } else if(a[a[i]].equals(a[i])){
                                              //初次发现重复，标记该数字出现2次
              if(number.get(a[i]) == null){
                       number.put(a[i],2);
                        break;
                    } else {
                       number.put(a[i],number.get(a[i])+1 );
                        break;
                    }
                                           //如果不相同就交换数字
          } else {
                    Integer b = a[i];
                    a[i] = a[b];
                    a[b] = b;
            }
         }
     }
            return number;
    }
}

2. 计算一个数组中某个元素的位置:

例如：

数组a[10][10],a[0][0] 的位置为1000，数组以行为序，则a[i][j] 的地址 =  a[0][0]地址 + i*每个元素需要存储空间+ j