sparsearray详解

一、什么是sparsearray

sparsearray（稀疏数组）是一种压缩存储数据的方式，它通常用于解决数据中存在大量空值（一般为默认值）的情况。稀疏数组是将二位数组转换为一维数组来节省存储空间的一种方法。

如果数组中大部分元素值为0或者同一个值时，我们就可以使用稀疏数组来代替原始的数组，从而节省内存空间。稀疏数组的转换方法为记录存储有值的元素的行列值以及对应的值，最后将这些元素存储到新的数组中。

// 稀疏数组的创建
int[][] chessArr = new int[11][11];
// 填充原数组
chessArr[1][2] = 1;
chessArr[2][3] = 2;
// 输出原数组
for (int[] row : chessArr) {
    for (int data : row) {
        System.out.printf("%d\t", data);
    }
    System.out.println();
}

// 将原数组压缩为稀疏数组
int sum = 0;
for (int i = 0; i < 11; i++) {
    for (int j = 0; j < 11; j++) {
        if (chessArr[i][j] != 0) {
            sum++;
        }
    }
}
int[][] sparseArr = new int[sum + 1][3];
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;
int count = 0;
for (int i = 0; i < 11; i++) {
    for (int j = 0; j < 11; j++) {
        if (chessArr[i][j] != 0) {
            count++;
            sparseArr[count][0] = i;
            sparseArr[count][1] = j;
            sparseArr[count][2] = chessArr[i][j];
        }
    }
}

// 输出稀疏数组
for (int[] row : sparseArr) {
    for (int data : row) {
        System.out.printf("%d\t", data);
    }
    System.out.println();
}

二、sparsearray的应用场景

sparsearray适用于当数据中某些元素的值非常规律且大量为同一个值时；或者当元素值很大且大部分为0时，可以使用稀疏数组来保存这些数据。下面是一些实际应用场景：

1.棋盘

一张棋盘大部分情况下都是没有棋子的，而只有少数的点放置了棋子。因此我们可以使用稀疏数组来节省存储空间。

int[][] chessBoard = new int[11][11];
chessBoard[1][2] = 1;
chessBoard[2][3] = 2;
int[][] sparseArr = toSparseArr(chessBoard);

2、象棋

象棋是一种对称性较高的棋类，当仅有一方存在棋子时，我们可以使用稀疏数组来保存信息。

int[][] checkerboard = new int[10][9];
checkerboard[0][0] = 1;
int[][] sparseArr = toSparseArr(checkerboard);

3、数组操作记录

当我们需要对一个数组进行多次操作并记录每次操作的结果时，可以使用稀疏数组来记录这些操作。

int[][] arr = new int[3][3];
arr[0][2] = 1;
arr[1][1] = 2;
int[][] sparseArr = toSparseArr(arr);
// 对稀疏数组中的元素进行操作
sparseArr[1][2] = 3;
int[][] arr2 = toArr(sparseArr);
for (int[] row: arr2) {
    for (int data : row) {
        System.out.printf("%d\t", data);
    }
    System.out.println();
}

三、sparsearray的应用示例

下面是一个动态展示将稀疏数组转换回原始数组的过程：

import java.util.Arrays;

public class SparseArray {

    public static void main(String[] args) {
        // 创建原始二维数组 11 * 11
        // 0: 表示没有棋子， 1 表示黑子 2 表示蓝子
        int[][] chessArr1 = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        // 输出原始二维数组
        System.out.println("原始二维数组：");
        for (int[] row : chessArr1) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        // 转换成稀疏数组
        int[][] sparseArr = toSparseArr(chessArr1);
        // 输出稀疏数组
        System.out.println("稀疏数组：");
        for (int[] row : sparseArr) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        // 转换回原始二维数组
        int[][] chessArr2 = toArr(sparseArr);
        // 输出转换后的二维数组
        System.out.println("转换后的二维数组：");
        for (int[] row : chessArr2) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }

    /**
     * 将二维数组转换为稀疏数组
     * @param chessArr 二维数组
     * @return 稀疏数组
     */
    public static int[][] toSparseArr(int[][] chessArr) {
        // 原始数组共有多少个非0值
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr[i][j] != 0) {
                    sum++;
                }
            }
        }
        // 创建稀疏数组
        int[][] sparseArr = new int[sum + 1][3];
        // 为稀疏数组赋值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        // 遍历原始数组，将非0值存入稀疏数组
        int count = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[i][j];
                }
            }
        }
        return sparseArr;
    }

    /**
     * 将稀疏数组恢复成原始二维数组
     * @param sparseArr 稀疏数组
     * @return 原始二维数组
     */
    public static int[][] toArr(int[][] sparseArr) {
        // 创建原始二维数组
        int[][] arr = new int[sparseArr[0][0]][sparseArr[0][1]];
        // 遍历稀疏数组，将值赋给原始二维数组
        for (int i = 1; i < sparseArr.length; i++) {
            arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        return arr;
    }
}