稀疏数组基本概念

在我们存储有大量重复元素值的二维数组时,如果使用一般的二维数组可能会有大量重复元素,这样就会浪费空间,例如

0	0	0	0
0	0	1	0
0	0	0	2
0	0	0	0

实际只有两个有效数据,却存储了四行四列

稀疏数组表示

• 遍历该数组,记录实际有效数据的个数
• 稀疏数组的第一行表示需要被转换的数组有多少行多少列,有效数据是多少个
• 从第二行开始记录实际有效数据的行，列，以及实际数据
  上面的数组就可以表示成

4	4	2
1	2	1
2	3	2

实际不管什么二维数组都会转换成 有效数据行+1和三列的数组

代码实现如下

package suanfa;

/**
 * 稀疏数组
 */
public class SparseArray {
    public static void main(String[] args) {
        //初始化数据
        int [][]data = new int[4][4];
        data[1][2] = 1;
        data[2][3] = 2;
        printArr(data);
        int sparseArr[][] = transform(data,0);
        printArr(sparseArr);
    }

    /**
     * 转换稀疏数组
     * @param data 原数组
     * @param repeat 重复元素
     * @return 转换后的稀疏数组
     */
    public static int[][] transform(int[][] data,int repeat){
        int valid = 0;//有效数据
        int rowNum = data.length;//行
        int colNum = data[0].length;//列
        /**计算有效数据 */
        for (int[] datum : data) {
            for (int i : datum) {
                if(i != repeat) {
                    ++valid;
                }
            }
        }

        /**稀疏数组赋值*/
        int sparse [][] = new int[valid+1][3];
        sparse[0][0] = rowNum;
        sparse[0][1] = colNum;
        sparse[0][2] = valid;
        int sparseCurrentrow = 0;//稀疏数组当前存储到的行
        for(int i = 0;i<data.length;++i){
            for(int j = 0;j<data[i].length;++j){
                if(data[i][j] != repeat){
                    sparse[++sparseCurrentrow][0] = i;
                    sparse[sparseCurrentrow][1] = j;
                    sparse[sparseCurrentrow][2] = data[i][j];
                }
            }
        }

        return sparse;
    }

    /**
     * 输出二维数组
     * @param data 
     */
    public static void printArr(int data[][]){
        for(int i = 0;i<data.length;++i){
            for(int j = 0;j<data[i].length;++j){
                System.out.printf("%d\t",data[i][j]);
            }
            System.out.println();
        }
    }
}

运行结果如下

深度截图_选择区域_20191223164839.png

运用场景

例如,在保存游戏进度时,用二维数组来表示数据,就可以把数据转换成稀疏数组在保存到本地,例如五子棋盘中途保存等