Day17：稀疏数组的超细详解
稀疏数组的超细详解
一个含有大量重复元素的二维数组，我们可以提取其有效元素，压缩空间，整合为一个稀疏数组。
例如一个五子棋棋盘，我们将棋盘看作为一个二维数组，没有棋子的位置为0；黑棋为1；白棋为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
我们可以将这个棋盘上有棋子的地方进行提取，整合为一个稀疏数组
| 行 | 列 | 值 | |
|---|---|---|---|
| [0] | 11 | 11 | 2 |
| [1] | 1 | 2 | 1 |
| [2] | 2 | 3 | 2 |
该稀疏数组意为有一个11行11列的二维数组，有效元素为2个；第1行，第2列元素值为1；第2行，第3列的元素值为2；
接下来我们将五子棋转为二维数组，再整合为稀疏数组，再将稀疏数组还原为二维数组
//打印五子棋盘的二维数组
public class Demo{
public static void main(String[] args){
//将上面的五子棋盘转为二维数组
int[][]a=new int[11][11];//建立一个二维数组有11行11列
a[1][2]=1;
a[2][3]=2;//将有效元素对应的位置进行赋值
//打印二维数组
for(int[]b:a){//增强for循环的使用，因为a是二维数组，要先将二维数组中的一维数组遍历出去
for(int c:b){//此时b是a的元素，为一维数组，再次遍历，可以得到b中的每一个元素了
System.out.print(c+"\t");
}
System.out.println();//每一组元素遍历后换行
}
System.out.println("========================================");
//提取有效元素，整合为稀疏数组
//稀疏数组也是一个数组，我们可以根据上面表格进行模仿打印
//首先我们先将有效个数先提取出来
int sum=0;//先建立一个计数的变量；
for(int i=0;i<a.length;i++){
for(int j=0;j<a[i].length;j++){
if(a[i][j]!=0){
sum++;//当if执行一次，则计数一次；理解为当发现一个有效元素则计数一次
}
}
}System.out.println("有效元素的个数为："+sum);
//有效个数得到后，我们可以开始建立稀疏数组了
int count=0;//建一个计数变量
int[][] array=new int[sum+1][3];//观察稀疏数组，行数为有效元素的个数加1，列数为3；
array[0][0]=11;
array[0][1]=11;
array[0][2]=2;
for(int i=0;i<a.length;i++){
for(int j=0;j<a[i].length;j++){
if(a[i][j]!=0){
count++;//发现有效元素则计数
array[count][0]=i;//将发现的有效元素的行坐标赋值给稀疏数组该放的地方
array[count][1]=j;//将发现的有效元素的列坐标赋值给稀疏数组该放的地方
array[count][2]=a[i][j];//将发现的有效元素的值赋值给稀疏数组该放的地方
}
}
}//此时棋盘中的数组将位置、值的信息全部赋值给了稀疏数组array
//将稀疏数组打印出来，还是一样，用遍历的方式打印出来
//第一种打印方式：在列数很少的情况下，可以按行打印，一行一行打印出来
for(int i=0;i<array.length;i++){
System.out.println(array[i][0]+"\t"+array[i][1]+"\t"+array[i][1]);
}
//第二种方式：利用两个for循环将元素遍历出来
System.out.println("打印稀疏数组：");
for(int i=0;i<array.length;i++){
for(int j=0;j<array[i].length;j++){
System.out.ptint(array[i][j]+"\t");
}
System.out.println();//每一行打印完后换行
}
System.out.println("====================================================");
//我们在尝试将稀疏数组还原成二维数组
//还是一样，先建立一个数组作为还原后的二维数组
int[][] array1=int[array[0][0]][array[0][1]];//稀疏数组array的第0行的0、1列分别记录的的是二维数组的行列大小
//再将稀疏数组的有效元素记录的信息赋值给二维数组
for(int i=1;i<array.length;i++){//i从1开始是因为在稀疏数组中第二行是有效元素的信息
array1[array[i][0]][array[i][1]]=array[i][2];
//array[i][0]记录的是第一个有效元素在二维数组中的行；
//array[i][1]记录的是第一个有效元素在二维数组中的列；
//array[i][2]记录的是第一个有效元素二维数组中的值
}
//循环结束后，我们希望还原的二维数组array1已经赋值完了
//打印二维数组
System.out.println("还原后的二维数组：");
for(int[] i=0:array1){//二维数组将其一维数组遍历出来
for(int s:i){//将一维数组的元素遍历出来
System.out.print(s+"\t");
}
System.out.println();
}
}
}
你可能想看：