稀疏数组

0    0    0    0
0    0    0    0
1    0    2    0    
0    0    0    0
如上二维数组作为棋盘存储的话太占用空间，有太多无效的数据0

可以使用稀疏数组来优化，原理：记录棋盘行和列的大小，记录有效值的个数，然后分别记录有效值的下标
如：        
   row  col  val
　　4    4    2
　　2    0    1
　　2    2    2

二维数组转换稀疏数组的思路
1.遍历原始的二维数组，得到有效数据的个数sum
2.根据sum就可以创建稀疏数组，sparseArr int[sum+1][3]
3.将二维数组的有效数据存入到稀疏数组

稀疏数组转换原始的二维数组的思路
1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的棋盘
2.再读取稀疏数组后几行的数据，并赋值给原始的二维数组即可

//生成二维数组
int[][] arr1 = new int[4][4];
arr1[2][0] = 1;
arr1[2][2] = 2;
arr1[3][2] = 4;
int sum = 0; //数组有效个数
for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
        if (arr1[i][j] != 0) {
            sum++;
        }
        System.out.print(arr1[i][j] + "\t");
    }
    System.out.println();
}

//            创建稀疏数组
        int[][] arr2 = new int[sum + 1][3];
        arr2[0][0] = 4;
        arr2[0][1] = 4;
        arr2[0][2] = sum;
        int count = 0;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (arr1[i][j] != 0) {
                    count++;
                    arr2[count][0] = i;
                    arr2[count][1] = j;
                    arr2[count][2] = arr1[i][j];
                }
            }
        }
        
        //        稀疏数组转换二维数组
        int[][] arr3 = new int[arr2[0][0]][arr2[0][1]];
        for (int i = 1; i < arr2.length; i++) {
            arr3[arr2[i][0]][arr2[i][1]] = arr2[i][2];
        }

 

原文链接:https://www.cnblogs.com/xukangjia/p/11323819.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有