稀疏数组SparseArray

1. 稀疏数组介绍

当一个数组中的大部分元素都为0，或者大部分元素均为同一个值时，此时记录了很多没有意义的数据，可以用稀疏数组来保存该数组。

在稀疏数组中记录了原数组共有几行几列，有多少个不同的值以及不同值的元素的位置。稀疏数组将这些信息记录在一个小规模的数组当中，从而达到缩小程序规模的目的。

经典的应用场景包括：用户数量庞大的线上五子棋棋盘游戏（作为棋盘的二维数组中只有三种值，0表示未放置棋子，以及黑子和白子），另外在Android开发中也经常用到SparseArray的API。

2. 实例说明

3. 二维数组与稀疏数组相互转换

3.1 二维数组转稀疏数组

思路：1.遍历原始的二维数组，得到有效数据值的个数（非0值个数sum）

​2.根据sum以及稀疏数组“行不确定列为3”的特点，创建稀疏数组sparsearray[sum+1][3]

​3.将二维数组的有效值及其位置存放到稀疏数组中

        // 初始化11*11棋盘二维数组
        int chessArr1[][] = new int[11][11];
        // 0代表无落子 1代表黑子 2代表白子
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        chessArr1[1][3] = 1;
        // 增强for循环输出初始二维数组（棋盘）
        System.out.println("输出初始化棋盘：");
        for(int[] row:chessArr1){
            for(int data:row){
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        // 二维数组 转 稀疏数组
        // 遍历二维数组，记录有效值总数sum用于初始化sparsearray
        int sum = 0;
        for(int[] row:chessArr1){
            for(int data:row){
                if(data!=0) sum++;
            }
        }
        // 初始化sparsearray
        int sparseArr[][] = new int[sum+1][3];
        sparseArr[0][0] = chessArr1.length;
        sparseArr[0][1] = chessArr1.length;
        sparseArr[0][2] = sum;
        // 遍历二维数组，将有效值及其位置存入稀疏数组sparsearray
        // 定义一个计数器count，用于记录有效值
        int count = 0;
        for(int i=0; i<chessArr1.length; i++){
            for(int j=0; j<chessArr1.length; j++){
                if(chessArr1[i][j]!=0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }
        // 输出稀疏数组
        System.out.println("转化为稀疏数组：");
        for(int[] row:sparseArr){
            for(int data:row){
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

3.2 稀疏数组转二维数组

思路：1.根据sparsearray第一行的数据创建二维数组

​2.再读取后续几行的数据，将相应的有效值赋给二维数组的相应位置

        // 稀疏数组 转 二维数组
        // 根据sparsearray第0行初始化二维数组大小
        int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
        // 从第1行开始遍历，将有效值及其位置写入二维数组
        for(int i=1; i<sparseArr[0][2]+1; 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();
        }
    }