稀疏数组

1、稀疏数组为n行3列，第一行分别存储二维数组的行数、列数及非无用元素的个数；其他行存储非无用元素的行、列和值；比如一个二维数组中的大部分元素是0，还有其他的少部分的非0值，则可以用稀疏数组来存储以减少其内存消耗或者磁盘存储时的文件大小。

2、代码示例

    public static void main(String[] args) {
        int[][] arr = new int[][]{{0,0,0,0,0,0,0,0,0,0},
                                  {0,0,2,0,0,2,0,0,1,0},
                                  {2,1,1,1,1,2,0,2,0,0},
                                  {0,2,1,1,1,1,2,0,0,0},
                                  {0,0,1,2,2,2,2,1,0,0},
                                  {0,1,1,2,2,2,2,1,0,0},
                                  {1,0,2,1,0,2,1,0,0,0},
                                  {0,0,0,0,0,0,2,0,0,0},
                                  {0,0,0,0,0,0,0,1,0,0},
                                  {0,0,0,0,0,0,0,0,0,0}};

        int[][] convert = convert(arr);
        for (int i = 0; i < convert.length; i++){
            for (int j = 0; j < convert[i].length; j++) {
                System.out.print(convert[i][j] + "\t");
            }
            System.out.println("\n");
        }
        int[][] recover = recover(convert);
        for (int[] ints : recover) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println("\n");
        }
    }

    /**
     * 将五子棋棋盘二维数组转换为稀疏数组
     * 其中 1为黑子 2为白子 0为无子
     */
    public static int[][] convert(int[][] checkerboard){
        if (checkerboard == null){
            return null;
        }
        //遍历二维数组获取棋子的个数
        int pieceNum = 0;
        for (int i = 0; i < checkerboard.length; i++){
            for (int j = 0; j < checkerboard[i].length; j++) {
                int piece = checkerboard[i][j];
                if (piece != 0 && piece != 1 && piece != 2){
                    throw new RuntimeException("位置" + i + "-" + j + "存在无效数据：" + piece);
                }
                if (piece == 1 || piece == 2){
                    pieceNum++;
                }
            }
        }
        if (pieceNum == 0){
            return null;
        }
        //创建稀疏数组
        int[][] sparseArr = new int[pieceNum + 1][3];
        sparseArr[0] = new int[]{checkerboard.length,checkerboard[0].length,pieceNum};
        int row = 1;
        for (int i = 0; i < checkerboard.length; i++){
            for (int j = 0; j < checkerboard[i].length; j++) {
                if (checkerboard[i][j] != 0){
                    sparseArr[row++] =  new int[]{i,j,checkerboard[i][j]};
                }
            }
        }
        return sparseArr;
    }

    /**
     * 稀疏数组恢复为二维数组
     */
    public static int[][] recover(int[][] sparseArr){
        if (sparseArr == null){
            return null;
        }
        int[][] checkerboard = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 1; i < sparseArr.length; i++) {
            checkerboard[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        return checkerboard;
    }
}