网站开发工程师职业定位360网站推广客服电话

最近在学习java数据结构和算法，每个重点知识我都会以 “思想原理 + 代码 + 总结” 的方式写一篇博客，方便自己以后复习，并分享给大家。如有问题，欢迎指出。

下图是一个二维数组所对应的稀疏数组：

映射关系：对于一个二维数组，它所对应的稀疏数组的第一行存储的是二维数组的行，列和二维数组中有效值的个数。后面的几行分别存储的是二维数中有效值所在的行，列和它的实际值。

代码实现：

package com.guigu.sparsearray;public class SparseArray {public static void main(String[] args) {//创建一个11*11的二维数组	int chessArr1[][] = new int[11][11];chessArr1[0][2] = 5;chessArr1[1][2] = 1;chessArr1[2][3] = 2;chessArr1[4][5] = 2;//输出原始的二位数组System.out.println("原始的二维数组~~");for(int[] row : chessArr1) {for(int data : row) {System.out.print(data + " ");}System.out.println();}//将二维数组转为稀疏数组//1.先变历二维数组 	得到非0数据的个数int sum = 0;for(int i = 0;i < 11;i++) {for(int j = 0;j < 11;j++) {if(chessArr1[i][j] != 0) {sum += 1;}}}//2.创建对应的稀疏数组int sparseArr[][] = new int[sum+1][3];//给稀疏数组赋值sparseArr[0][0] = 11;sparseArr[0][1] = 11;sparseArr[0][2] = sum;//遍历二维数组，将非0值存放到sparseArr中int count = 0; //count用于几个是第几个非0数据for(int i = 0;i < chessArr1.length;i++) {for(int j = 0;j < chessArr1[i].length;j++) {if(chessArr1[i][j] != 0) {count++;sparseArr[count][0] = i;sparseArr[count][1] = j;sparseArr[count][2] = chessArr1[i][j];}}}//输出稀疏数组的形式System.out.println();System.out.println("稀疏数组的形式~~");for(int i = 0;i < sparseArr.length;i++) {for(int j = 0;j < sparseArr[i].length;j++) {System.out.print(sparseArr[i][j] + " ");}System.out.println();}//将稀疏数组转为二维数组/** 1.先读取稀疏数组的第一行，获取到原始二维数组的信息（行数，列数，有效值的个数）* 2.再读取稀疏数组的后几行数据，并赋给原始的二维数组即可。*///1.先读取稀疏数组的第一行，根据第一行数据，创建二维数组int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];//2.读取剩下每一行的数据，并赋给二维数组for(int i = 1;i < sparseArr.length;i++) {chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2]; }//输出恢复后的二维数组System.out.println();System.out.println("恢复后的二维数组~~");for(int[] row : chessArr2) {for(int data : row) {System.out.print(data + " ");}System.out.println();}}}

输出结果：

原始的二维数组~~
0 0 5 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 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 稀疏数组的形式~~
11 11 4 
0 2 5 
1 2 1 
2 3 2 
4 5 2 恢复后的二维数组~~
0 0 5 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 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 

总结：稀疏数组就是对二维数组的"压缩"，减少了空间的浪费。在代码实现过程中，注意要先求的二维数组中有效值的个数，才能确定稀疏数组除第一行外还有几行，才能准确创建稀疏数组；稀疏数组赋值时，在给除第一行外的其他值赋值时，要声明一个辅助变量，每次增加1，来存储二维数组有效值的信息，第一次赋值时就应该先加1，从二行开始存储。