稀疏数组

什么叫稀疏数组？
如果二维数组中的大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
相比与 二维数组而言，稀疏数组存放的数据更少，如果通过稀疏数组的方式存入信息，会占用更小的磁盘空间
而且，就如五子棋而言，我们只需要存棋子的信息，没有棋子的位置都是一个值，那么我们何必将这些默认值也存到磁盘中呢？

稀疏数组一般有 n行3列
稀疏数组的第一行会存放
二维数组的行，二维数组的列，二维数组的有效值
其余行数存放
有效值的行，有效值的列，有效值

image.png

二维数组转稀疏数组

  1. 遍历原始的二维数组，获取有有效值的个数sum
  2. 然后形成 int[sum+1][3] 的稀疏数组
  3. 二维数组的有效数据存入到 稀疏数组

稀疏数组还原成二维数组

  1. 稀疏数组转 二维数组
  2. 读取稀疏数组的第一行，然后创建二维数组
  3. 读取稀疏数组后几行的数据，然后赋给原始数组

代码实现

  1. public class SparseArray {
  2.     public static void main(String[] args) {
  3.         //创建一个原始的二维数组 用来表示五指棋的棋盘
  4.         //0 表示没有棋子 1 表示黑子 2 表示白子
  6.         int[][] chessArr1 = new int[11][11];
  7.         chessArr1[1][2] = 1;
  8.         chessArr1[2][3] = 2;
  9.         chessArr1[4][5] = 2;
  11.         System.out.println("原始二维数组：");
  12.         for (int[] row : chessArr1) {
  13.             for (int col : row) {
  14.                 System.out.printf("%d\t",col);
  15.             }
  16.             System.out.println();
  17.         }
  19.         /*
  20.         二维数组转 稀疏数组
  21.         遍历原始的二维数组，获取有有效值的个数sum
  22.         然后形成 int[sum+1][3] 的稀疏数组
  23.         二维数组的有效数据存入到 稀疏数组
  24.         */
  25.         int sum = 0;
  26.         for (int i = 0; i < 11; i++) {
  27.             for(int j = 0; j < 11; j++) {
  28.                 if (chessArr1[i][j] != 0) {
  29.                     sum++;
  30.                 }
  31.             }
  32.         }
  34.         System.out.println("有效值一共有"+ sum +"个");
  36.         //创建对应的 稀疏数组并初始化
  37.         int[][] sparseArr = new int[sum+1][3];
  38.         //第一列存放有 多少行，多少列，多少个有效值
  39.         sparseArr[0][0] = 11;
  40.         sparseArr[0][1] = 11;
  41.         sparseArr[0][2] = sum;
  43.         //然后将有效值的信息存入到其他行
  44.         //比如第一个有效值是1 在 第二行的第三列，那么就设置成 1 2 1
  45.         int row = 1;//记录第几个有效值
  46.         for (int i = 0; i < 11; i++) {
  47.             for(int j = 0; j < 11; j++) {
  48.                 if (row > sum) {
  49.                     break;
  50.                 }
  51.                 if (chessArr1[i][j] != 0) {
  52.                     sparseArr[row][0] = i;
  53.                     sparseArr[row][1] = j;
  54.                     sparseArr[row][2] = chessArr1[i][j];
  56.                     row++;
  57.                 }
  58.             }
  59.         }
  61.         System.out.println();
  62.         System.out.println("压缩后的稀疏数组：");
  63.         //输出稀疏数组
  64.         for (int i = 0; i < sparseArr.length; i++) {
  65.             System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
  66.         }
  68.         /*
  69.         稀疏数组转 二维数组
  71.          读取稀疏数组的第一行，然后创建二维数组
  72.          读取稀疏数组后几行的数据，然后赋给原始数组
  74.          */
  75.         int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
  77.         for (int i = 1; i <= sparseArr[0][2]; i++) {
  78.             chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
  79.         }
  81.         System.out.println("还原后的二维数组：");
  82.         for (int[] r : chessArr2) {
  83.             for (int col : r) {
  84.                 System.out.printf("%d\t",col);
  85.             }
  86.             System.out.println();
  88.         }
  89.     }
  90. }