稀疏数组

1. 稀疏数组的作用就是将数组压缩成更小的数组，一般这个数组里面包含比较多的同一个元素。

2. 实现思想：

   1. 稀疏数组的第一行分别记录原数组的行数，列数，不同数的个数。
   2. 稀疏数组接下来每一行记录每一个原数组的行坐标，列坐标，坐标值。

3. 代码实现如下：

   //稀疏数组
   public class SparseArray {
       public static void main(String[] args) {
           //创建一个原始数组  11x11
           int[][] preArr = new int[11][11];
           preArr[1][2] = 1;
           preArr[2][3] = 2;
           
           //打印原数组的值
           System.out.println("原数组:");
           printArray(preArr);
   
           //遍历二维数组，得到非0数据的个数
           int sum = 0;
           for (int i = 0; i < preArr.length; i++) {
               for (int j = 0; j < preArr[i].length; j++) {
                   if (preArr[i][j] != 0) {
                       sum++;
                   }
               }
           }
   
           System.out.println("sum=" + sum);
   
           //创建对应的稀疏数组
           int[][] sparseArray = new int[sum + 1][3];
           //给稀疏数组赋值(第一行)
           sparseArray[0][0] = preArr.length;
           sparseArray[0][1] = preArr[0].length;
           sparseArray[0][2] = sum;
   
           //遍历二维数组，将非0值存放到稀疏数组中
           int count = 0;  //用于的记录是第几个非0数据
           for (int i = 0; i < preArr.length; i++) {
               for (int j = 0; j < preArr[i].length; j++) {
                   if (preArr[i][j] != 0) {
                       count++;
                       //把就数组中的非0写入稀疏数组对应的位置中
                       sparseArray[count][0] = i;
                       sparseArray[count][1] = j;
                       sparseArray[count][2] = preArr[i][j];
                   }
               }
           }
   
           //遍历稀疏数组的值
           System.out.println("稀疏数组为 :");
           //printArray(sparseArray);
   
           //将稀疏数组恢复成二维数组
           /**
            * 思路： 1.读取稀疏数组的第一行,获取到原数组的行数和列数，
            *       2.再读取稀疏数组后面几行，，并赋予原始数组即可
            */
   
           System.out.println("回复后的二维数组为:");
           int[][] afterArray = new int[sparseArray[0][0]][sparseArray[0][1]];
           for (int i = 1; i < sparseArray.length; i++) {
               //稀疏数组的第i行第0列是原数组的行数
               //稀疏数组的第i行第1列是原数组的列数
               //稀疏数组的第i行第2列是原数组的值
               afterArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
           }
   
           System.out.println("恢复后为:");
           printArray(afterArray);
       }
   
       public static void printArray(int[][] arr) {
           for (int i = 0; i < arr.length; i++) {
               for (int j = 0; j < arr[i].length; j++) {
                   System.out.print(arr[i][j] + "\t");
               }
               System.out.println();
           }
       }
   }
   

4. 打印结果为:

   原数组:
   0 0 0 0 0 0 0 0 0 0 0
   0 0 1 0 0 0 0 0 0 0 0
   0 0 0 2 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   sum=2
   稀疏数组为 :
   11 11 2
   1 2 1
   2 3 2
   回复后的二维数组为:
   回复后为:
   0 0 0 0 0 0 0 0 0 0 0
   0 0 1 0 0 0 0 0 0 0 0
   0 0 0 2 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0
   0 0 0 0 0 0 0 0 0 0 0

   Process finished with exit code 0