稀疏数组
一、介绍
当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组,也可以理解为压缩数组。
稀疏数组的处理方法:
- 记录数组一共有几行几列,有多少个不同的值。
- 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模。
二、实例
- 使用稀疏数组,来保留类似前面的二维数组(棋盘、地图等等)
- 把稀疏数组存盘,并且可以从新恢复原来的二维数组数
- 整体思路分析:
首先需要将二维数组转换为稀疏数组,然后再将稀疏数组写入到磁盘文件中
通过磁盘文件读取稀疏数组,然后再转换为原来数组
二维数组转稀疏数组的思路:
- 遍历原始的二维数组,得到有效数据的个数sum
- 根据sum就可以创建稀疏数组 spareArray = int [sum+1] [3]
- 将二维数组的有效数据存入到稀疏数组
稀疏数组转原始数组的思路:
- 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二位数组,比如上面的array = int [11] [11]
- 在读取稀疏数组后几行的数据,并赋给原始的二维数组即可
三、代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
| public class SparseArray { public static void main(String[] args) { int[][] array = new int[11][11]; array[1][2] = 1; array[2][3] = 2;
System.out.println("原始的二维数组:"); for (int[] row : array) { for (int value : row) { System.out.printf("%d\t",value); } System.out.println(); }
int sum = 0; for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (array[i][j] != 0) sum++; } } int[][] sparseArray = new int[sum + 1][3]; sparseArray[0][0] = 11; sparseArray[0][1] = 11; sparseArray[0][2] = sum;
int count = 0; for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (array[i][j] != 0) { count++; sparseArray[count][0] = i; sparseArray[count][1] = j; sparseArray[count][2] = array[i][j]; }
} }
System.out.println(); System.out.println("得到的稀疏数组为"); for (int i = 0; i < sparseArray.length; i++) { System.out.printf("%d\t%d\t%d\t\n",sparseArray[i][0], sparseArray[i][1], sparseArray[i][2]); } int array2[][] = new int[ sparseArray[0][0] ][ sparseArray[0][1]] ; for (int i = 1; i < sparseArray.length; i++) { array2[ sparseArray[i][0] ][ sparseArray[i][1] ] = sparseArray[i][2]; } System.out.println(); System.out.println("恢复后的二维数组为"); for (int[] row : array2) { for (int value : row) { System.out.printf("%d\t",value); } System.out.println(); }
} }
|
输出如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| 原始的二维数组: 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
得到的稀疏数组为 11 11 2 1 2 1 2 3 2
恢复后的二维数组为 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
|