本文共 2910 字，大约阅读时间需要 9 分钟。

稀疏数组（Sparse Array）是一种优化后的数据结构，特别适用于存储具有大量零元素的二维数组。现代计算机中，内存是不可逆的资源，稀疏数组通过减少存储零元素的空间，提高了内存利用效率，避免由于大量零元素占用内存而浪费资源的问题。

稀疏数组的结构

稀疏数组是一个由多行组成的数组。第一行为元数据，包含三个元素：

• 原始数组的行数（rows）
• 原始数组的列数（cols）
• 原始数组中非零元素的总个数（sum）

后面的每一行依次记录原始数组中的非零元素，包含以下三个信息：

• 原始数组中的行索引（i）
• 原始数组中的列索引（j）
• 对应元素的值（value）

例如，如果原始数组是一个11x11的棋盘，其中有两个非零元素分别位于（1,2）和（2,3）、（3,4），那么稀疏数组的结构如下：

• 第一行：11, 11, 3
• 第二行：1, 2, 1
• 第三行：2,3,2
• 第四行：3,4,2

###이드疏数组的转换思路

二维数组转稀疏数组

稀疏数组转二维数组

代码实现

package com.datastrucate.sparsearray;
public class SparseArray {
    public static void main(String[] args) {
        // 二维数组例子，棋盘位置，1代表黑子，2代表白子，0代表空位
        int[][] chessArr = new int[11][11];
        chessArr[1][2] = 1;     // (1,2) 位置有黑子
        chessArr[2][3] = 2;     // (2,3) 位置有白子
        chessArr[3][4] = 2;     // (3,4) 位置有白子
        // 计算非零元素个数
        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; // 非零元素个数
        // 填充稀疏数组，每行依次存储非零元素的i、j和值
        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) {
            for (int value : row) {
                System.out.print(value + " ");
            }
            System.out.println();
        }
        // 稀疏数组转二维数组
        int[][] recoveredArr = new int[sparseArr[0][0]][sparseArr[0][1]];
        // 填充恢复后的数组
        for (int i = 1; i < sparseArr.length; i++) {
            int row = sparseArr[i][0];
            int col = sparseArr[i][1];
            int value = sparseArr[i][2];
            recoveredArr[row][col] = value;
        }
        // 输出恢复后的二维数组
        System.out.println("恢复后的二维数组");
        for (int[] arr : recoveredArr) {
            for (int value : arr) {
                System.out.print(value + " ");
            }
            System.out.println();
        }
    }
}

总结

稀疏数组通过存储元数据和仅记录非零元素的位置和值，有效地减少了内存占用。对于存储大量零元素的二维数组来说，这种结构非常有用。通过上述代码，可以实现二维数组到稀疏数组的转换，以及反过来稀疏数组到二维数组的还原。这对优化内存使用具有重要意义，特别是在处理大型数据集时。