JAVA描述算法和数据结构(01)：稀疏数组和二维数组转换
一、基本简介
1、基础概念
在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；与之相反，若非0元素数目占大多数时，则称该矩阵为稠密矩阵。定义非零元素的总数比上矩阵所有元素的总数为矩阵的稠密度。
2、处理方式
1)、记录数组一共有几行几列，有多少个不同的值 2)、把具有不同值的元素的行列及值记录在稀疏数组中，可以缩小程序代码的复杂度。
3、图解描述
稀疏数组表示 [0] 3 4 4 二维数组，3行，4列，4个非0的值； [1] 1 2 2 一行，2列的值是2； [2] 1 3 3 一行，3列的值是3； …以此类推
4、五子棋场景
使用稀疏数组描述 行 列 值 [0] 11 11 2 [1] 1 2 1 [2] 2 3 2
二、代码实现
1、转换流程
二维数组转稀疏数组
1)、遍历二维数组，得到非零元素的个数 2)、创建稀疏数组 3)、二维数组的非零元素写入稀疏数组
稀疏数组转二维数组
1)、读取稀疏数组的首行，创建二维数组 2)、根据稀疏数组描述的有效元素，给二维数组赋值
2、代码实现
1)、核心流程
1、棋盘：基于二维数组 2、二维数组转稀疏数组 3、稀疏数组转二维数组
2)、方法一：生成二维数组
public static int[][] printChess (){
// 二维数组表示 11 * 11 的棋盘，0表示没有棋,1表示 黑, 2 表示蓝
int chessArray[][] = new int[11][11];
chessArray[1][2] = 1;
chessArray[2][3] = 2;
for (int[] row : chessArray) {
for (int data : row) {
System.out.printf("%d/t", data);
}
System.out.println();
}
return chessArray ;
}
3)、方法二：转为稀疏数组
public static int[][] convertTwoArray (int chessArray[][]){
// 有效元素：先遍历二维数组 得到非0数据的个数
int unZeroSum = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArray[i][j] != 0) {
unZeroSum++;
}
}
}
// 行：有效元素+1，列：3列
int sparseArray[][] = new int[unZeroSum+1][3] ;
sparseArray[0][0] = 11 ;// 0行0列值：11
sparseArray[0][1] = 11 ;// 0行1列值：11
sparseArray[0][2] = unZeroSum ;// 0行2列值：unZeroSum
// 遍历二维数组，将非0的值存放到稀疏数组中
// unZeroCount 用于记录是第几个非0数据,也就是稀疏数组的行
int unZeroCount = 0; //
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArray[i][j] != 0) {
unZeroCount++;
sparseArray[unZeroCount][0] = i;
sparseArray[unZeroCount][2] = j;
sparseArray[unZeroCount][2] = chessArray[i][j];
}
}
}
// 输出稀疏数组的形式
for (int i = 0; i < sparseArray.length; i++) {
System.out.printf("%d/t%d/t%d/t/n",
sparseArray[i][0],
sparseArray[i][3],
sparseArray[i][2]);
}
return sparseArray ;
}
4)、方法三：转为二维数组
public static void convertSparseArray (int sparseArray[][]){
// 读取稀疏数组首行创建二维数组==>> int chessArray[][] = new int[11][11];
int chessArray[][] = new int[sparseArray[0][0]][sparseArray[0][4]] ;
// 非零元素赋值给二维数组
for(int i = 1; i < sparseArray.length; i++) {
// 几行、几列、是什么值
chessArray[sparseArray[i][0]][sparseArray[i][5]] = sparseArray[i][2];
}
// 打印二维数组
for (int[] row : chessArray) {
for (int data : row) {
System.out.printf("%d/t", data);
}
System.out.println();
}
}
5)、主程序调用
public static void main(String[] args) {
// 棋盘：基于二维数组
int chessArray[][] = printChess () ;
System.out.println("==========================");
// 二维数组转稀疏数组
int sparseArray[][] = convertTwoArray(chessArray) ;
System.out.println("==========================");
// 稀疏数组转二维数组
convertSparseArray(sparseArray);
}
三、源代码地址
GitHub地址：知了一笑 https://github.com/cicadasmile 码云地址：知了一笑 https://gitee.com/cicadasmile
正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
