Java多维数组及稀疏数组
如何理解多维数组
数组大家应该都是了解一些的，这里先从二维数组开始说起：可以将它理解为一个存放着数组的数组，能够表示一个二维平面的行列集合，和关系型数据库中的一张表格非常相似。
再向后延伸，三维数组就可以理解为一个存放二维数组的数组。
看到二维，三维这样的字眼，难免会想到生活中也提到的维度，比如一种普遍的说法，人是生活在四维空间的三维生物。
这个话题再展开就扯太远了，这里只想做一下类比，多维数组以及关系型数据库，和生活中所说的维度，点线面体非常相似。
零维的点，相当于数组中的一个数据，或数据库表中的一个单元格；
一维的线，相当于一整个数组，或数据库表中的一行；
二维的面，相当于一个二维数组，或者一张数据库表；
三维的体，相当于多个二维数组的集合，或多张表的集合；
再向后，超过了四维，生活中的维度就很难想象了，但数组的维度向后推去并没有什么阻力，四维数组也不过就是三维数组的集合......
根据上面的说法，再来拿二维数组举例，就可以产生丰富的应用场景。
首先可以当做关系型数据库表格来用，比如存放一张成绩单
此外，也完全可以将二维数组用来表示一个平面，例如棋盘、迷宫、推箱子地图等
Java中的数组
这里只介绍普通数组和二维数组，高维数组语法也是相同的可自行类比
在Java中声明一个数组整体来归类可分为两种方式
静态初始化和动态初始化
/*普通数组*/
//数据类型 [] 变量名称 = new 数据类型[]{xxx,xxx,xxx};声明加静态初始化,xxx表示数组中的数据
int [] arr = new int[]{1,2,3};
//数据类型 [] 变量名称 = new 数据类型[i];声明加动态初始化,i表示数组容量
int [] arr = new int[5];
/*二维数组*/
//数据类型 [][] 变量名称 = new 数据类型[][]{{xx,xx},{xx,xx},{xx}};静态初始化
//数据类型 [][] 变量名称 = new 数据类型[i][j];动态初始化，可以没有j，但必须有i
//如果不指定列，就需要在使用时动态再初始化列
int arr[][] = new int[2][];//此时如果直接想要调用arr[0][0]会报错空指针，因为没有给列开辟空间
//还需要以这样的方式再给列初始化
arr[0] = new int[2];
//注意，等号前的中括号可以随意摆放，以下方式都是可以的，但等号后的括号不能乱动
int []a[];
int a[][];
int [][]a;
int a[];
int []a;
//也要注意，等号前面的括号必须是空的
//动态静态两种方式不能结合使用，比如下面这样就是错误的
int [] arr = new int[5]{1,2,3,4,5};
注意：
Java中的数组是不可扩容的，也就是声明时就已经确定了数组的容量
jvm给声明的数组分配的内存空间是连续的，声明后就必须被固定了，不支持后续更改空间容量，因为后边连续的空间可能被其他内容占用
所以无论哪种声明方式，都会在声明时就确定了数组的容量
静态初始化和动态初始化的区别：
静态方式会自动根据赋值的数据开辟数组的空间，同时存放上相应的数据
这里需要注意，多维数组中不一定是四方的,不同行可能不一样长，要小心边界超出范围
//比如下面这样会报错 java.lang.ArrayIndexOutOfBoundsException
int [][] arr = new int[][]{{1,2,3},{4,5},{6}};
System.out.println(arr[1][3]);
动态方式会根据指定长度开辟内存空间，对数据进行初始化
初始化的方式：
1.如果是整型，int long short：数据会被初始化为0
2.如果是浮点型，float double：数据会被初始化为0.0
3.如果是boolean型：数据会被初始化为false
4.如果是引用类型（除基本类型外都是引用类型）：数据会被初始化为null
5.如果是char型：数据会被初始化为0或'\u0000'，注意不是'0'，这是一个空格符但还不是键盘上的空格......所以想要判断char型数组是否是没有数据的可以判断的方式只能是{arr[0]==0或者arr[0]=='\u0000'}不可以是{arr[0]==' '}
二维数组与稀疏数组
先用二维数组来画一个11*11的五子棋盘
采用int数组，因为初始化数据都是0，所以用0表示空，1表示黑棋，2表示白棋
int [][] chessArr = new int[11][11];
遍历一下二维数组，打印在控制台看一下
//遍历二维数组需要一个嵌套循环
for (int[] row : arr) {
for (int data : row) {
System.out.print(data+"\t");
}
System.out.println();
}
可以看到如下的效果
给它添加上几个棋子再打印
//假设当前棋盘第二行第三列一枚黑子，第三行第四列一枚白子，第八行第十列有一枚黑子
chessArr[1][2] = 1;
chessArr[2][3] = 2;
chessArr[7][9] = 1;
看到如下打印
可以发现，当二维数组中有效数据较少的时候，被大量无意义的0占用了内存空间
是不是有什么办法可以简化一下二维数组呢？
这时就有人想到了一种办法并将其命名为稀疏数组：
稀疏数组中，只去记录有效的数据
1.记录二维数组的总行数，总列数，有效数据数量
2.记录每一个有效数据所在行，所在列，数据值
根据上述两条的数据就可以通过一定的计算完整还原出二维数组
那么对于上面这个11行11列的二维数组，只需要一个4行3列的二维数组就可以取代
对于很多场景，可以做到对内存或存储空间的节省
下面演示一下用Java代码实现二维数组到稀疏数组的转换
编码思路无非就是获得下面这三个我们需要的关键数据，再保存到一个新的数组作为稀疏数组返回即可
1.原二维数组的总行数、总列数
2.数组中有效数据的个数（遍历一遍，非0就是有效的）
3.每一个有效数据所在的位置和数值（再遍历一遍，获取到这些信息插入到稀疏数组）
注意：第一次遍历得到的数据要用来重建稀疏数组的时候初始化行数，第二次遍历就已经在创建好稀疏数组后插入数据了，所以虽然两次都是遍历原数组，但不能合并成一次遍历进行
这里还可以对是否值得转换进行一个判断：
二维数组占用的内存空间为总行数*总列数
稀疏数组占用的内存空间为有（有效数据个数+1）*3
如果（有效数据个数+1）* 3 >= 总行数 * 总列数就会失去转换意义
/**
* 二维数组转换为稀疏数组
* @param chessArr 二维数组
* @return 返回稀疏数组
*/
private static int[][] getSparseArr(int[][] chessArr) {
//获得二维数组中非0数据的个数
int sum = 0;
for (int[] row : chessArr) {
for (int data : row) {
if (data!=0){
sum++;
}
}
}
//判断是否值得创建稀疏数组
if ((sum+1)*3 >= chessArr.length * chessArr[0].length){
System.out.println("该二维数组其实不值得转换为稀疏数组");
}
//创建稀疏数组，列数固定为3，行数为非0数据的个数加一
int[][] sparseArr = new int[sum+1][3];
//稀疏数组第一行直接进行赋值
//行数
sparseArr[0][0] = chessArr.length;
//列数
sparseArr[0][1] = chessArr[0].length;
//非0数据个数
sparseArr[0][2] = sum;
//后续表示具体数据的行，遍历赋值
//count记录当前是第几个非0数据
int count = 0;
//遍历出每一行，i表示第几行的索引（第一行就是0）
for (int i = 0; i < chessArr.length; i++) {
//遍历当前行的每个数据，j表示第几列（第一列就是0）
for (int j = 0; j < chessArr[i].length; j++) {
//判断是否为非0数据
if (chessArr[i][j]!=0){
//找到一个非0数据计数器+1
count++;
//给稀疏数组赋值，行、列、值
sparseArr[count][0] = i+1;
sparseArr[count][1] = j+1;
sparseArr[count][2] = chessArr[i][j];
}
}
}
return sparseArr;
}
稀疏数组转换回二维数组
稀疏数组保存起来节省空间，但需要检索或展示的时候，还是变回二维数组更加方便
所以再演示一个反转的代码实例
/**
* 稀疏数组转二维数组
* @param sparseArr 稀疏数组
* @return 返回转换后的二维数组
*/
private static int[][] getNewChessArr(int[][] sparseArr) {
//创建新的二维数组作为转换回的二维数组——行列数为稀疏数组第一行前两列存放的行列数
int[][] newChessArr = new int[sparseArr[0][0]][sparseArr[0][1]];
//遍历把非0数据插入进去
for (int i = 0; i < sparseArr.length; i++) {
if (i!=0){
newChessArr[sparseArr[i][0]-1][sparseArr[i][1]-1] = sparseArr[i][2];
}
}
return newChessArr;
}
