02 数据结构与算法之稀疏数组

介绍

当一个数组中大部分元素为0，或者为同一个值时，可以用稀疏数组来保存该数组

稀疏数组的处理方法

1. 记录数组中一共有几行几列，有多少个不同的值
2. 把具有不同值的元素的行、列及值记录在一个小规模的数组中，从而缩小程序的规模。

二维数组：

转换后的稀疏数组：

说明：第一行存储数组有多少行，多少列，多少个有效值。后面的所有行分别记录有效值的行号和列号。

代码实现

• 二维数组转换为稀疏数组
  1、遍历原始的二维数组，得到有效数据的个数sum
  2、根据sum，就可以创建稀疏数组sparseArr int[sum + 1][3]
  3、将二维数组的有效数据存入到稀疏数组

  	//创建一个原始的二维数组 11*11
      //0：没有棋子  1：黑子  2：蓝子
      int[][] chessArr1 = new int[11][11];
      for(int i = 0; i<chessArr1.length; i++){
          for(int j = 0; j<chessArr1[i].length; j++)
              chessArr1[i][j] = 0;
      }
      chessArr1[1][2] = 1;
      chessArr1[2][3] = 2;
      
  	//将二维数组转稀疏数组
      //1、先遍历二维数组，得到非0数据的个数
      int sum = 0;
      for(int i = 0; i < chessArr1.length; i++){
          for(int j = 0; j < chessArr1[i].length; j++){
              if(chessArr1[i][j] != 0)
                  sum++;
          }
      }
  
      //2、创建稀疏数组
      int sparseArr[][] = new int[sum + 1][3];
      //给稀疏数组赋值
      sparseArr[0][0] = chessArr1.length;
      sparseArr[0][1] = chessArr1[0].length;
      sparseArr[0][2] = sum;
      //遍历二维数组，将非0值填入稀疏数组
      int rows = 1;  //记录往稀疏数组的第几行填值
      for(int i = 0; i < chessArr1.length; i++){
          for(int j = 0; j < chessArr1[i].length; j++){
              if(chessArr1[i][j] != 0){
                  sparseArr[rows][0] = i;
                  sparseArr[rows][1] = j;
                  sparseArr[rows++][2] = chessArr1[i][j];
              }
          }
      }
  

• 稀疏数组恢复成二维数组

  
  //将稀疏数组恢复成二维数组
      int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
      for(int i = 0; i<sparseArr[0][2]; i++){
          chessArr2[sparseArr[i+1][0]][sparseArr[i+1][1]] = sparseArr[i+1][2];
      }