线性结构之稀疏数组 sparse-array

1. 需求：编写五子棋程序，有存盘和读盘的功能。

image.png

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

稀疏数组的处理方法：

1. 记录数组一共有几行几列，有多少个不同的值

2. 把具有不同值的元素的行列以及值记录在一个小规模的数组中，从而缩小程序的规模。
   例子：

   
   image.png
   

   6行7列变成了9行3列，稀疏数组固定都是3列。

2. 应用实例

使用稀疏数组来表示棋盘的二维数组来存盘，再将稀疏数组恢复成二维数组棋盘实现读盘。
row  col  value
11   11   2      -- 11行11列，2个有效数字
1    2    1      -- 第一行第二列，值为1
2    3    2      -- 第二行第三列，值为2

二维数组转稀疏数组思路：

1. 遍历二维数组，得到有效值的个数sum
2. 根据sum创建稀疏数组sparse-array int[sum + 1][3]
3. 将二维数组的有效数据存入到稀疏数组

稀疏数组转二维数组思路：

1. 先读取稀疏数组第一行，根据第一行的数据创建原始的二维数组（第一行的前两个值就是行数和列数）
2. 再读取稀疏数组后几行的数据，并赋给原始的二维数组

3. 代码

用vscode写的，文件是utf8的，但是注释却是gbk的，不知道为什么，就是javac的时候老报错，只能删了注释来运行。

-- 查了下资料，“由于JDK是国际版的，我们在用javac编译时，编译程序首先会获得我们操作系统默认采用的编码格式（GBK），然后JDK就把Java源文件从GBK编码格式转换为Java内部默认的Unicode格式放入内存中，然后javac把转换后的Unicode格式的文件编译成class类文件，此时，class文件是Unicode编码的，它暂存在内存中，紧接着，JDK将此以Unicode格式编码的class文件保存到操作系统中形成我们见到的class文件。当我们不加设置就编译时，相当于使用了参数：javac -encoding GBK Test.java，就会出现不兼容的情况。”
https://github.com/toyranger/data_structure_algorithm.git

package com.ds.sparse.array;

public class SparseArray {

  public static void main(String[] args) {

    int[][] chessArray = genChessArray();
    printArray(chessArray);

    System.out.println("------------------------------");
    int[][] trans2SparseArr = trans2SparseArr(chessArray);
    printArray(trans2SparseArr);

    System.out.println("------------------------------");
    int[][] trans2ChessArr = trans2ChessArr(trans2SparseArr);
    printArray(trans2ChessArr);

  }

  /***
   * 生成原始的棋盘二维数组
   * @return
   */
  private static int[][] genChessArray() {

    int[][] chessArray = new int[11][11];

    chessArray[1][2] = 1;
    chessArray[2][3] = 2;

    return chessArray;
  }

  /***
   * 遍历打印数组
   * @param array
   */
  private static void printArray(int[][] array) {

    for (int[] tmpArr : array) {
      for (int value : tmpArr) {
        System.out.printf("%d\t", value);
      }

      System.out.println();
    }
  }

  /***
   * 获取二维数组中有效值个数
   * @param array
   * @return
   */
  private static int getValidValueCnt(int[][] array) {

    int cnt = 0;

    for (int[] tmpArr : array) {

      for (int tmpVal : tmpArr) {

        if (0 != tmpVal) {

          cnt++;
        }
      }
    }

    return cnt;
  }

  /***
   * 二维数组转成稀疏数组
   * @param chessArr
   * @return
   */
  private static int[][] trans2SparseArr(int[][] chessArr) {

    int valueCnt = getValidValueCnt(chessArr);
    int[][] sparseArr = new int[valueCnt + 1][3];

//    第一行是原始二维数组的行数列数和有效值
    int rowCnt = chessArr.length;
    int colCnt = chessArr[0].length;
    sparseArr[0][0] = rowCnt;
    sparseArr[0][1] = colCnt;
    sparseArr[0][2] = valueCnt;

//    遍历棋盘数组，每找到一个有效值，对应稀疏数组的行数加一，并且把有效值的行和列以及值存入该行
    int sparseRow = 1;
    for (int row = 0; row < rowCnt; row++) {
      for (int col = 0; col < colCnt; col++) {

        int value = chessArr[row][col];

        if (0 != value) {
          sparseArr[sparseRow][0] = row;
          sparseArr[sparseRow][1] = col;
          sparseArr[sparseRow][2] = value;
          sparseRow++;
        }
      }
    }

    return sparseArr;
  }

  /***
   * 稀疏数组还原成二维数组
   * @param sparseArr
   * @return
   */
  private static int[][] trans2ChessArr(int[][] sparseArr) {

    int rowCnt = sparseArr[0][0];
    int colCnt = sparseArr[0][1];

    int[][] chessArr = new int[rowCnt][colCnt];

//    从第二行开始遍历稀疏数组，把有效值填入棋盘数组对应的行和列位置
    for (int rowNumOfSparse = 1; rowNumOfSparse < sparseArr.length; rowNumOfSparse++) {
      int rowNum = sparseArr[rowNumOfSparse][0];
      int colNum = sparseArr[rowNumOfSparse][1];
      int value = sparseArr[rowNumOfSparse][2];

      chessArr[rowNum][colNum] = value;
    }

    return chessArr;
  }
}