浅谈Java数据结构之稀疏数组知识总结

稀疏数组的定义

稀疏数组是指当一个数组中大部分元素是相同的值时，可以使用稀疏数组来保存该数组。稀疏数组的必要性在于节省内存空间，当数组中元素过多时，存储数组所需的内存空间也呈指数级增长。

稀疏数组的特点

1. 稀疏数组存储的是一个原始的二维数组。
2. 稀疏数组的第一行保存原始数组的基本信息，包括行数、列数、有效值的个数。
3. 稀疏数组的每一行保存一个有效的数据信息，包括该元素所在行数、列数以及该元素的值。

稀疏数组的应用场景

稀疏数组的应用场景很多，以下是两个实践案例。

1. 棋盘问题
   如果一个棋盘中有N个子，且大多数子都是0，那么这个棋盘的数组可以使用稀疏数组来存储。保存该棋盘所消耗的内存空间明显小于保存该棋盘的数组所需的空间。

下面的代码示例演示了如何将一个棋盘转换成稀疏数组以及如何将稀疏数组还原成一个棋盘：

public class SparseArray {

    public static void main(String[] args) {
        // 原始棋盘
        int[][] chessArr = new int[11][11]; 
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        chessArr[4][5] = 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];
                }
            }
        }
        // 输出稀疏数组
        System.out.println("稀疏数组为：");
        for (int[] row : sparseArr) {
            System.out.printf("%d\t%d\t%d\n", row[0], row[1], row[2]);
        }
        // 将稀疏数组还原成原始数组
        int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 1; i < sparseArr.length; i++) {
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        // 输出还原后的原始数组
        System.out.println("还原后的原始数组为：");
        for (int[] row : chessArr2) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
}

1. 历史文件记录
   稀疏数组还可以应用于记录历史文件，比如著名的UNIX系统中，记录用户使用情况的wtmp文件。这个文件保存进入系统和退出系统的时间、用户名、终端号等信息。一般情况下，这些记录都是空的，只有在有用户进入和退出系统的时候才会进行记录。将这个文件记录成稀疏数组，可以大大节省存储空间。

稀疏数组的注意事项

1. 稀疏数组也是一个二维数组，平时使用时需要特别注意行列顺序。
2. 稀疏数组的第一行必须保存原始数组的基本信息，否则无法完整还原原始数组。