稀疏数组

基本介绍

稀疏数组可以看作是普通数组的压缩，当一个数组中大部分元素为0或同一个值时，可用稀疏数组来保存该数组

使用目的

1. 源数组中存在大量的无效数据，占据了大量存储空间，真正有用的数据却很少
2. 压缩存储可以有效地利用资源，避免资源的无效浪费，当数据序列化到磁盘时，压缩存储可以提高压缩效率

实现思路

1，稀疏数组的第一列表示原数组行数，第二列表示原数组列数，第三列表示值

2，第一行存放，原数组几行，几列，共有几个不一样的值

3，随后的每一行都存放的是特殊值的位置（行，列）及值

1. 普通数组转稀疏数组：

   <1>遍历原始二维数组得到有效数据（非0）的个数sum;

   <2>根据sum（确定稀疏数组的大小）创建稀疏数组 ";

   <3>将二维数组的有效数据存入稀疏数组>将二维数组的有效数据存入稀疏数组;

2. 稀疏数组转普通数组：

   <1>先读取稀疏数组的第一行，根据第一行来创建原始二维数组

   <2>2，读取稀疏数组的后几行数据赋值给原始的二维数组

图解

代码实现

1. 普通二维数组转稀疏数组：

   /**
    * 普通数组转稀疏数组
    * @param arr；传入普通二维数组
    * @return：返回此二维数组对应的稀疏数组
    */
   public static int[][] transSpareArr(int[][] arr){
       int sum=0;//sum：源数组中有效数据的个数
       //循环遍历源数组获得源数组中有效数据的个数
       for(int[] nums:arr){
           for(int num:nums){
               if(num!=0){
                   sum++;
               }
           }
       }
       int[][] sparArr=new int[3][sum+1];//创建稀疏数组
       sparArr[0][0]=arr.length;//源数组有几行
       sparArr[0][1]=arr[0].length;//源数组有几列
       sparArr[0][2]=sum;//源数组有几个有效数据
       int count=1;//用来记录是第几个非零数据
       for(int i=0;i<arr.length;i++){
           for(int j=0;j<arr[i].length;j++){
               if(arr[i][j]!=0){
                   sparArr[count][0]=i;//第一列记录有效数据在源数组的所在行
                   sparArr[count][1]=j;//第二列记录有效数据在源数组的所在列
                   sparArr[count][2]=arr[i][j];//有效数据的值
                   count++;
               }
           }
       }
       return sparArr;
   }
   

2. 稀疏数组转普通二维数组：

   /**
    * 稀疏数组转普通数组
    * @param sparArr:传入稀疏数组
    * @return：返回相对应的原数组
    */
   public static int[][] transArr(int[][] sparArr){
       //根据稀疏数组的第0行数据创建源数组对象
       // 稀疏数组第0行的第一列存储源数组共几行，稀疏数组第0行的第二列存储的是源数组共几列
       int[][] arr=new int[sparArr[0][0]][sparArr[0][1]];
       //遍历稀疏数组，将有效数据存入源数组相对应的位置
       for(int i=1;i<sparArr.length;i++){
           arr[sparArr[i][0]][sparArr[i][1]]=sparArr[i][2];
       }
       return arr;
   }