Day17:稀疏数组的超细详解

2023-01-08

稀疏数组的超细详解

一个含有大量重复元素的二维数组,我们可以提取其有效元素,压缩空间,整合为一个稀疏数组。

例如一个五子棋棋盘,我们将棋盘看作为一个二维数组,没有棋子的位置为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();
} }
}

Day17:稀疏数组的超细详解的相关教程结束。