Java稀疏数组的应用实践

什么是稀疏数组

在Java的数组中，大部分的数组元素都是非零元素。如果一个二维数组中非零元素的个数远远小于数组元素总数时，我们通常称这个二维数组为稀疏数组。

稀疏数组可以通过压缩算法来减少存储空间，常见的稀疏数组压缩方式是压缩成一个一维数组，其中每个元素保存非零元素的值及其所在的索引位置，从而达到节省空间的目的。

稀疏数组的应用场景

当我们需要处理大量稀疏数据时，稀疏数组就可以发挥其作用。例如，我们家里的书店，我们需要跟踪库存并记录每本书的销售记录，但是我们卖的书很多，我们总不能把每本书都存储在一个数组中吧？这时候，我们就可以使用稀疏数组来记录每本书的销售记录，使用稀疏数组的话，我们就只需要记录非零元素的值及其所在位置，从而节省了很多的空间。

稀疏数组的实现方法

稀疏数组可以通过压缩算法来实现，使用一个二维数组来保存稀疏数组的值及其所在的索引位置，然后再将这个二维数组压缩成一个一维数组即可。

以下是一个实现稀疏数组的示例：

public class SparseArray {
    public static void main(String[] args) {
        // 创建一个二维数组
        int[][] arr = new int[4][5];
        arr[0][1] = 1;
        arr[1][2] = 2;
        arr[2][3] = 3;

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

        // 将稀疏数组压缩为一维数组
        int[][] sparseArray = compressSparseArray(arr);
        System.out.println("压缩后的稀疏数组：");
        for (int[] row : sparseArray) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        // 将压缩后的稀疏数组恢复为原始数组
        int[][] newArr = restoreSparseArray(sparseArray);
        System.out.println("恢复后的数组：");
        for (int[] row : newArr) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }

    /**
     * 将稀疏数组压缩为一维数组
     *
     * @param arr 稀疏数组
     * @return 一维数组
     */
    public static int[][] compressSparseArray(int[][] arr) {
        // 统计稀疏数组中非零元素的个数
        int sum = 0;
        for (int[] row : arr) {
            for (int data : row) {
                if (data != 0) {
                    sum++;
                }
            }
        }

        // 创建一个一维数组
        int[][] sparseArr = new int[sum + 1][3];

        // 设置稀疏数组的第一行
        sparseArr[0][0] = arr.length;
        sparseArr[0][1] = arr[0].length;
        sparseArr[0][2] = sum;

        // 遍历原始数组，将非零元素保存在稀疏数组中
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = arr[i][j];
                }
            }
        }

        return sparseArr;
    }

    /**
     * 将一维数组恢复为稀疏数组
     *
     * @param sparseArray 一维数组
     * @return 稀疏数组
     */
    public static int[][] restoreSparseArray(int[][] sparseArray) {
        int row = sparseArray[0][0];
        int col = sparseArray[0][1];
        int[][] newArr = new int[row][col];

        for (int i = 1; i < sparseArray.length; i++) {
            int r = sparseArray[i][0];
            int c = sparseArray[i][1];
            int value = sparseArray[i][2];
            newArr[r][c] = value;
        }

        return newArr;
    }
}

实例介绍

下面我们用两个实例来介绍稀疏数组的应用。

实例一：五子棋游戏

五子棋游戏是一种非常受欢迎的棋类游戏，我们可以使用稀疏数组来存储棋盘，从而达到减少存储空间的目的。以下是一个使用稀疏数组实现五子棋游戏的示例：

public class Gobang {
    private static final int ROW = 15;
    private static final int COL = 15;

    public static void main(String[] args) {
        int[][] chessBoard = new int[ROW][COL];
        // 初始化棋盘
        initChessBoard(chessBoard);

        // 输出棋盘
        System.out.println("当前棋盘：");
        printChessBoard(chessBoard);

        // 下棋
        int x = 7;
        int y = 7;
        int chess = 1;
        putChess(chessBoard, x, y, chess);

        // 输出棋盘
        System.out.println("当前棋盘：");
        printChessBoard(chessBoard);

        // 将棋盘压缩为稀疏数组
        int[][] sparseArr = compressSparseArray(chessBoard);
        System.out.println("压缩后的稀疏数组：");
        printSparseArray(sparseArr);

        // 将稀疏数组恢复为棋盘
        int[][] newArr = restoreSparseArray(sparseArr);
        System.out.println("恢复后的棋盘：");
        printChessBoard(newArr);
    }

    /**
     * 初始化棋盘
     *
     * @param chessBoard 棋盘
     */
    private static void initChessBoard(int[][] chessBoard) {
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COL; j++) {
                chessBoard[i][j] = 0;
            }
        }
    }

    /**
     * 输出棋盘
     *
     * @param chessBoard 棋盘
     */
    private static void printChessBoard(int[][] chessBoard){
        for (int[] row : chessBoard) {
            for (int value : row) {
                System.out.print(value + " ");
            }
            System.out.println();
        }
    }

    /**
     * 下棋
     *
     * @param chessBoard 棋盘
     * @param x x坐标
     * @param y y坐标
     * @param chess 棋子的值
     */
    private static void putChess(int[][] chessBoard, int x, int y, int chess) {
        if (chessBoard[x][y] == 0) {
            chessBoard[x][y] = chess;
        }
    }
}

实例二：地图矩阵

地图矩阵是一个非常常见的应用场景，我们可以将一个非常大的地图压缩成稀疏数组，从而减少存储空间。以下是一个使用稀疏数组实现地图矩阵的示例：

public class MapMatrix {
    public static void main(String[] args) {
        // 创建一个地图矩阵
        int[][] map = new int[1000][1000];
        for (int i = 0; i < 1000; i++) {
            for (int j = 0; j < 1000; j++) {
                map[i][j] = (int) (Math.random() * 10);
            }
        }

        // 输出地图矩阵
        System.out.println("原始地图矩阵：");
        for (int[] row : map) {
            for (int data : row) {
                System.out.printf("%d ", data);
            }
            System.out.println();
        }

        // 将地图矩阵压缩为稀疏数组
        int[][] sparseArr = compressSparseArray(map);
        System.out.println("压缩后的稀疏数组：");
        printSparseArray(sparseArr);

        // 将稀疏数组恢复为地图矩阵
        int[][] newArr = restoreSparseArray(sparseArr);
        System.out.println("恢复后的地图矩阵：");
        for (int[] row : newArr) {
            for (int data : row) {
                System.out.printf("%d ", data);
            }
            System.out.println();
        }
    }
}

上述示例中，我们首先创建了一个随机的地图矩阵，然后将其压缩为稀疏数组，并将稀疏数组恢复为原始地图矩阵。通过这个示例，我们可以了解到稀疏数组的另一个非常实用的应用场景。