稀疏数组可以看做是普通二维数组的压缩，为什么要对数组进行压缩呢？常见的场景是地图，棋盘。这些容器都是行和列组成的二维数组，在数组中的一些点上标记着特殊的位置。但是这些标记位相对于整个二维数组来说只使用了一小部分，数组中剩余的部分都是默认值。如果我们将一个地图存储到用户的磁盘中，会造成不必要的空间浪费。于是才有了稀疏数组对二维数组进行压缩。

二维数组转换稀疏数组的思路是

1 确定二维数组的行，列，标记点的个数，用于还原二维数组。

2 找到每一个标记点所在的行，列和值。

3 将1，2构成一个新的N行3列的稀疏数组。

例如二维数组是8*8的矩阵，实际的标记点只有三个，其余的全是默认值0。

 

转换成稀疏数组后是4*3的二维数组，其中第一行记录了源数组的行，列，标记点个数。剩余三行则记录了标记点的位置和值。

 

最后附上代码

public static void main(String[] args) {
        int[][] twoArray = new int[8][8];
        twoArray[1][3] = 1;
        twoArray[3][1] = 2;
        twoArray[6][7] = 3;
        System.out.println("源数组");
        showArray(twoArray);

        int[][] sparseArray = twoArrayToSparseArray(twoArray);
        System.out.println("稀疏数组");
        showArray(sparseArray);

        int[][] twoArray2 = sparseArrayToTwoArray(sparseArray);
        System.out.println("稀疏数组转源数组");
        showArray(twoArray2);
    }

    public static int[][] twoArrayToSparseArray(int[][] twoArray) {
        int count = 0;
        for (int i = 0; i < twoArray.length; i++) {
            for (int x = 0; x < twoArray[i].length; x++) {
                if (twoArray[i][x] != 0) {
                    count++;
                }
            }
        }

        int line = 1;
        int[][] sparseArray = new int[count + 1][3];
        sparseArray[0][0] = twoArray.length;
        sparseArray[0][1] = twoArray[0].length;
        sparseArray[0][2] = count;

        for (int i = 0; i < twoArray.length; i++) {
            for (int x = 0; x < twoArray[i].length; x++) {
                if (twoArray[i][x] != 0) {
                    sparseArray[line][0] = i;
                    sparseArray[line][1] = x;
                    sparseArray[line][2] = twoArray[i][x];
                    line++;
                }
            }
        }
        return sparseArray;
    }

    public static int[][] sparseArrayToTwoArray(int[][] sparseArray) {
        int line = sparseArray[0][0];
        int row = sparseArray[0][1];
        int[][] twoArray = new int[line][row];
        for (int i = 1; i < sparseArray.length; i++) {
            int line2 = sparseArray[i][0];
            int row2 = sparseArray[i][1];
            int value = sparseArray[i][2];
            twoArray[line2][row2] = value;
        }
        return twoArray;
    }

    public static void showArray(int[][] array) {
        for (int i = 0; i < array.length; i++) {
            for (int x = 0; x < array[i].length; x++) {
                System.out.print(array[i][x] + " ");
            }
            System.out.println();
        }
    }

View Code

 

版权声明：本文为zumengjie原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/zumengjie/p/13769853.html