当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组时,可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:
(1)记录数组一共有几行几列,有多少个不同的值
(2)把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模
如下图所示为二维数组与其对应的稀疏数组:
(1)二维数组转稀疏数组的思路:
1.遍历原始的二维数组,得到有效数据的个数sum
2.根据sum就可以创建稀疏数组sparseArr int [sum + 1][3]
3.将二维数组的有效数据存入到稀疏数组
(2)稀疏数组转原始的二维数组的思路:
1.先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组
2.再读取稀疏数组后几行的数据,并赋给原始的二维数组即可
思路看完后是不是还是觉得有点抽象呢?下面直接上代码进行直观的演示说明???
package com.java.datastructures;
/**
* Author:YuHao
* Description: 二维数组与稀疏数组之间的转换
* Date:2022/7/13
* Version:1.0
*/
public class SparseArray {
public static void main(String[] args) {
//(一)二维数组转为稀疏数组
//创建一个二维数组,数组大小为11*11 (五子棋盘)
//0表示没有旗子,1表示为黑子,2表示为白子
int chessArr1[][] = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
chessArr1[7][8] = 1;
//1.遍历原始数组,通过增强for循环实现
System.out.println("(1)二维数组转稀疏数组");
System.out.println("原始二维数组如下所示:");
for (int [] row : chessArr1){
for (int data : row){
System.out.print(data+"\t");
}
System.out.println();
}
//2.找出二维数组当中的非零值总数
int sum = 0;
System.out.println("二维数组中非零值总数为:");
for (int i = 0; i < chessArr1.length; i++){
for (int j = 0; j < chessArr1.length; j++){
if (chessArr1[i][j] != 0){
sum ++;
}
}
}
System.out.println("sum = "+sum);
//3.创建稀疏数组
int spareArr[][] = new int [sum + 1][3];
//4.给稀疏数组赋值
spareArr[0][0] = 11;
spareArr[0][1] = 11;
spareArr[0][2] = sum;
int count = 0 ; //count为计数器
for (int i = 0; i < chessArr1.length; i++){
for (int j = 0; j < chessArr1.length; j++){
if (chessArr1[i][j] != 0){
count ++;
spareArr[count][0] = i;
spareArr[count][1] = j;
spareArr[count][2] = chessArr1[i][j];
}
}
}
//5.遍历稀疏数组
System.out.println("所创建的稀疏数组为:");
for (int i = 0; i < sum + 1; i++){
for (int j = 0; j < 3; j++){
System.out.print(spareArr[i][j]+"\t");
}
System.out.println();
}
//(二)稀疏数组转原始二维数组
System.out.println("(2)稀疏数组转原始二维数组");
//1.读取稀疏数组第一行,创建二维数组
int chessArr2[][] = new int [spareArr[0][0]][spareArr[0][1]];
//2.读取稀疏数组后几行,赋值给二维数组
for (int i = 1; i < sum + 1; i++){
chessArr2[spareArr[i][0]][spareArr[i][1]] = spareArr[i][2];
}
//3.遍历原始二维数组
System.out.println("恢复后的二维数组为:");
for (int [] row : chessArr2){
for (int data : row){
System.out.print(data + "\t");
}
System.out.println();
}
}
}
代码执行后的效果如下所示???
路过的小伙伴,如果博文有帮助到你解决问题,可以点赞+收藏+关注一波呀~本人将会持续更新相关数据结构与算法Java实现版本学习的博文,感谢您的支持哦!!!芜湖起飞✈️✈️✈️