算法之稀疏数组
当一个数组的元素包含大量的0时,或者为同一个值的数组时,可以使用稀疏数组来保存数组.
稀疏数组的处理方法:
1,记录数组一共有几行几列,有多少个不同的值
2,把具有不同值的元素的行列及值记录在一个小规模的数组(稀疏数组)中,从而缩小程序的规
实例讲解:
图片中的二维数组转换成稀疏数组
二维数组转稀疏数组
publicclassSparesArry{
publicstaticvoidmain(String[]args) {
intchessArry1[][]=newint[11][11];
chessArry1[1][2]=1;
chessArry1[2][3]=2;
for(int[]arr:chessArry1) {
for(intdata:arr) {
System.out.printf("%d\t",data);
}
System.out.println();
}
// 原始二维数组
intsum=0;
for(inti=0;i<chessArry1.length;i++) {
for(intj=0;j<chessArry1.length;j++) {
if(chessArry1[i][j]!=0) {
sum++;
}
}
}
// 遍历原始数组统计数值
intsparesarry[][]=newint[sum+1][3];
sparesarry[0][0]=11;// 行数
sparesarry[0][1]=11;// 列数
sparesarry[0][2]=sum;// 统计数
// 遍历数组存值,讲原数组信息存贮到稀疏数组里
intcount=0;
for(inti=0;i<chessArry1.length;i++) {
for(intj=0;j<chessArry1.length;j++) {
if(chessArry1[i][j]!=0) {
count++;
sparesarry[count][0]=i;
sparesarry[count][1]=j;
sparesarry[count][2]=chessArry1[i][j];
}
}
}
System.out.println();
// 打印稀疏数组
for(intc=0;c<sparesarry.length;c++) {
System.out.printf("%d\t%d\t%d\t\n",sparesarry[c][0],sparesarry[c][1],sparesarry[c][2]);
}
System.out.println();
// 将稀疏数组还原成原数组
// 1.先读取稀疏数组第一行,根据第一行数据信息,创建出二维数组
// 2/读取稀疏数组后面几行,并将数据添加到二维数组中
intchessArry2[][]=newint[sparesarry[0][0]][sparesarry[0][1]];
for(inti=1;i<sparesarry.length;i++) {// 从第二行开始读取数据
chessArry2[sparesarry[i][0]][sparesarry[i][1]]=sparesarry[i][2];
}
System.out.println();
for(int[]arr:chessArry2) {
for(intdata:arr) {
System.out.printf("%d\t",data);
}
System.out.println();
}
}
}
