Java编写稀疏数组

稀疏数组"/>

Java编写稀疏数组

稀疏数组
当一个数组中大部分元素为0，或者为同一个值时，可以使用稀疏数组来存储数组。
稀疏数组的处理方法
1.记录数组一共有几行几列，有多少不同的值。

2.把具有不同值的元素的行列和值存放在一个小规模的数组中，该小规模数组就是稀疏数组。

如下图

如下图，这是一个棋盘，底层的数据可以用数组表示，其中棋盘没有棋子的时候可以表示为0，黑棋子可以表示为1，蓝色棋子表示为2。所以，当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来存放该数组。


得到的稀疏数组是

		row 	col 	val0	11		11		21	1		2		12	2		3		2

二维数组转稀疏数组的思路
1.遍历二维数组，统计有效数据的个数sum
2.根据sum就可以创建稀疏数组，列如

int[][] array1 = new int[sum+1][3];

3.将二维数组的有效数据存放在稀疏数组中
稀疏数组转化为原来的二维数组的思路
1.首先，读取稀疏数组的第一行，根据第一行的数据创建为原来的二位数组
2.再读取稀疏数组的后几行数据，并赋值给原始的二维数组
代码

package A1;public class Teat09 {public static void main(String[] args) {//创建原始二位数组，并赋值int[][] array = new int[11][11];array[1][2]=1;array[2][3]=2;array[3][4]=2;//打印数组for (int[] a:array) {for (int a1:a) {System.out.print(a1+"\t");}System.out.println();}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++;}}}System.out.println("统计有效值个数:"+sum);//创建稀疏数组，将二位数组的行列赋值给稀疏数组第一行int[][] array1 = new int[sum+1][3];array1[0][0] = 11;array1[0][1] = 11;array1[0][2] = sum;//遍历二维数组，将非零的值存放在稀疏数组中int count=0;for (int i = 0; i < array.length; i++) {for (int j = 0; j < array[i].length; j++) {if(array[i][j]!=0){count++;array1[count][0]=i;array1[count][1]=j;array1[count][2]=array[i][j];}}}//打印稀疏数组for (int i = 0; i < array1.length; i++) {System.out.println(array1[i][0]+"\t"+array1[i][1]+"\t"+array1[i][2]);}System.out.println("=====================");//将稀疏数组还原为二维数组int[][] array2 = new int[array1[0][0]][array1[0][1]];for (int i = 1; i < array1.length; i++) {array2[array1[i][0]][array1[i][1]] = array1[i][2];}for (int[] t:array2) {for (int t1:t) {System.out.print(t1+"\t");}System.out.println();}}
}

结果如图