稀疏数组

0    0    0    0
0    0    0    0
1    0    2    0    
0    0    0    0 如上二维数组作为棋盘存储的话太占用空间，有太多无效的数据0 可以使用稀疏数组来优化，原理：记录棋盘行和列的大小，记录有效值的个数，然后分别记录有效值的下标 如： row col val 　　4    4    3
　　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]; }