前言：
稀疏数组是一种为了节约存储空间而产生的数据结构，本质上稀疏数组就是一个普通的二维数组。其实在真实的应用中，稀疏数组的用武之地很少，起码笔者工作了几年，是没有发现稀疏数组的用武之地的（感觉游戏领域可能会用到），但是作为数据结构的一种，我们学习他还是可以得到一些启发的，比如使用时间换空间的思想，反过来使用空间换时间不也是可以的吗。所以学习他不一定非要用，但是肯定会对自己的思维有帮助。
一、稀疏数组介绍
1.什么是稀疏数组
在多维数组中，若是存在大量重复值，那么我们可以选择，将重复值排除掉，只保留那些有意义的数据，将这些有意义信息存入到一个二维数组中，这个二维数据就叫做稀疏数组，在原始数组是二维数组时，稀疏数组就是一个普通的n行3列的二维数组，下面也将以此场景来聊聊稀疏数组。
2.稀疏数组的实现原理
稀疏数组是一个n行3列的二维数组，那为什么是3列呢？仔细分析下就可以明白，在原始的二维数组中一个有效数据包含了3个必须记录的信息，即：行数、列数、值。只要记录了这三个值，我们就可以将原来的二维数组转变为稀疏数组，同样的有了这三个值，我们还可以将稀疏数组还原到原来的二维数组，这样也就明白了稀疏数组实现的原理了，原理就是只记录原二维数组中的有效数据，记录的是有效数据的行、列、值，这三个值构成了稀疏数组的一个行，所以一行有三列。不过这些记录是可以还原数组的所有的有效数据，但是我们并不清楚原数据到底有多少行多少列啊，所以还需要记录原始数组的行、列、有效数据的个数。这三个值一般放在数组的第0行。
3.稀疏数组规律
根据以上信息我们轻易的可以发现稀疏数组是一个这样的结构：（原始数组有效数据个数+1）行，3列的二维数组。假设原有数组是x行y列有n个有效数据那我们可以得出这么一个公式：xy>(n+1)3,这样我们使用稀疏数组才会有意义（此时稀疏数组节点个数小于原二维数组），不然使用稀疏数组，既浪费了时间，也没有节约空间。所以假如要使用稀疏数组这个是必须判断的。比如有一个10行9列的二维数组，所以我们可以得出这个公式：90>(n+1)*3,可以发现n<29时也就是有效数据小于29时，我们使用稀疏数组是节约了空间的，此时使用稀疏数组才是有意义的。当然事实上可能这个临界值并不是一个好的判断节点，可能要空间节约很多时，才能弥补的上原始二维数组转化为细稀疏数组带来的性能消耗。这里只是提供一个判断思路。
二、稀疏数组的实现
这里总结下，二维数组转稀疏数组和稀疏数组转二维数组的过程。
1.将二维数组转化为稀疏数组
首先明确思路：第一步我们应该获取到原数组的行数列数，以及有效数据的个数。第二步就是遍历原二维数据将有效数据存入到稀疏数组。这就是我们的实现思路，然后跟着思路去实现代码，如下：
//二维数组有效数据个数 static int countValid = 0; /** * 将二维数组转变为稀疏数组sparsearray * 实现思路： * 1.首先确定二维数组中有效数据的个数，用以得到稀疏数组的行数：二维数组有效数据个数+1 * 2.将二维数组中有效数据，存入到稀疏数组中 * 3.返回稀疏数组 * @param twoDimensionArray * @return */ public static int[][] changeTwoDimensionToSparseArray(int[][] twoDimensionArray){ //判断数组是否有效 if(twoDimensionArray.length>0 && twoDimensionArray[0].length>0){ //通过一次遍历获取到所有有效数据 Arrays.stream(twoDimensionArray).forEach(intArray ->{ Arrays.stream(intArray).forEach(intNum ->{ if(intNum!=0){ countValid++; } }); }); //创建稀疏数组,并将第一列值创建出来分别是：二维数组行数、列数、有效数据个数 int[][] newSparseArray = new int[countValid+1][3]; newSparseArray[0][0]=twoDimensionArray.length; newSparseArray[0][1]=twoDimensionArray[0].length; newSparseArray[0][2]=countValid; //定义稀疏数组行初始值 int line = 1; //遍历二维数组，将有效数据传入到稀疏数组中 for(int i=0;i<twoDimensionArray.length;i++){ for(int j=0;j<twoDimensionArray[i].length;j++){ if(twoDimensionArray[i][j]!=0){ newSparseArray[line][0]=i; newSparseArray[line][1]=j; newSparseArray[line][2]=twoDimensionArray[i][j]; line++; } } } return newSparseArray; } return null; }
2.将稀疏数组转化为二维数组
首先明确思路：第一步根据稀疏数组第一行信息创建二维数组，第二步遍历稀疏数组取出信息放入二维数组中。这样我们就可以实现将稀疏数组返显到二维数组了。
/** * 稀疏数组转变为二维数组 * 实现逻辑： * 1.根据稀稀数组第一行的信息，创建二维数组。 * 2.遍历二维数组，将信息取出，放入到二维数组中。 * 3.返回二维数组 * @param sparseArray * @return */ public static int[][] changeSparseArrayToTwoDimension(int[][] sparseArray){ //判断稀疏数组是否有效 if(sparseArray.length>0 && sparseArray[0].length>0){ //根据二维数组创建稀疏数组 int[][] twoDimensionArray = new int[sparseArray[0][0]][sparseArray[0][1]]; //遍历稀疏数组，将有效数据取出，存入到二维数组 for(int i=0;i<sparseArray.length;i++){ //第一行非有效数据，不取 if(i>0){ //二维数组有效元素的行数是，i行0列，二维数组的列数是i行1列，二维数组有效元素值是i行2列 twoDimensionArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2]; } } return twoDimensionArray; } return null; }
3.简单的数组打印方法
再封装一个简单的数组打印方法，供来回测试调用。
//打印二维数组 public static void printArray(int[][] thisArray){ Arrays.stream(thisArray).forEach(intArray ->{ Arrays.stream(intArray).forEach( intValue ->{ System.out.print(intValue); }); System.out.println(); }); }
4.测试结果
写一段测试代码，如下，测试下程序运行是否得到了想要的结果：
public static void main(String[] args) { int[][] firstArray = new int[10][10]; firstArray[3][4] = 1; firstArray[0][6] = 1; firstArray[2][3] = 1; printArray(firstArray); System.out.println("***********************************************************"); //调用二维数组转稀疏数组方法 int[][] sparseArray = changeTwoDimensionToSparseArray(firstArray); printArray(sparseArray); System.out.println("***********************************************************"); //调用稀疏数组转二维数组方法 int[][] twoDimensionArray = changeSparseArrayToTwoDimension(sparseArray); printArray(twoDimensionArray); }
下面展示下输出结果：
上图中第一部分是原始数组信息，第二部分是稀疏数组，第三部分是稀疏数组转换的二维数组，从上面的图片中我们可以看到无论是二维数组转稀疏数组，还是稀疏数组转化为二维数组，都没有任何问题。这样所有的功能也就实现了。
4.贴下完整的代码
上面代码都是分段展示的，这里贴下完整的代码。
public class TestSparseArray { //因为使用lamdba，需要将其定义为类变量 //二维数组有效数据个数 static int countValid = 0; public static void main(String[] args) { int[][] firstArray = new int[10][10]; firstArray[3][4] = 1; firstArray[0][6] = 1; firstArray[2][3] = 1; printArray(firstArray); System.out.println("***********************************************************"); //调用二维数组转稀疏数组方法 int[][] sparseArray = changeTwoDimensionToSparseArray(firstArray); printArray(sparseArray); System.out.println("***********************************************************"); //调用稀疏数组转二维数组方法 int[][] twoDimensionArray = changeSparseArrayToTwoDimension(sparseArray); printArray(twoDimensionArray); } //打印二维数组 public static void printArray(int[][] thisArray){ Arrays.stream(thisArray).forEach(intArray ->{ Arrays.stream(intArray).forEach( intValue ->{ System.out.print(intValue); }); System.out.println(); }); } /** * 将二维数组转变为稀疏数组sparsearray * 实现思路： * 1.首先确定二维数组中有效数据的个数，用以得到稀疏数组的行数：二维数组有效数据个数+1 * 2.将二维数组中有效数据，存入到稀疏数组中 * 3.返回稀疏数组 * @param twoDimensionArray * @return */ public static int[][] changeTwoDimensionToSparseArray(int[][] twoDimensionArray){ //判断数组是否有效 if(twoDimensionArray.length>0 && twoDimensionArray[0].length>0){ //通过一次遍历获取到所有有效数据 Arrays.stream(twoDimensionArray).forEach(intArray ->{ Arrays.stream(intArray).forEach(intNum ->{ if(intNum!=0){ countValid++; } }); }); //创建稀疏数组,并将第一列值创建出来分别是：二维数组行数、列数、有效数据个数 int[][] newSparseArray = new int[countValid+1][3]; newSparseArray[0][0]=twoDimensionArray.length; newSparseArray[0][1]=twoDimensionArray[0].length; newSparseArray[0][2]=countValid; //定义稀疏数组行初始值 int line = 1; //遍历二维数组，将有效数据传入到稀疏数组中 for(int i=0;i<twoDimensionArray.length;i++){ for(int j=0;j<twoDimensionArray[i].length;j++){ if(twoDimensionArray[i][j]!=0){ newSparseArray[line][0]=i; newSparseArray[line][1]=j; newSparseArray[line][2]=twoDimensionArray[i][j]; line++; } } } return newSparseArray; } return null; } /** * 稀疏数组转变为二维数组 * 实现逻辑： * 1.根据稀稀数组第一行的信息，创建二维数组。 * 2.遍历二维数组，将信息取出，放入到二维数组中。 * 3.返回二维数组 * @param sparseArray * @return */ public static int[][] changeSparseArrayToTwoDimension(int[][] sparseArray){ //判断稀疏数组是否有效 if(sparseArray.length>0 && sparseArray[0].length>0){ //根据二维数组创建稀疏数组 int[][] twoDimensionArray = new int[sparseArray[0][0]][sparseArray[0][1]]; //遍历稀疏数组，将有效数据取出，存入到二维数组 for(int i=0;i<sparseArray.length;i++){ //第一行非有效数据，不取 if(i>0){ //二维数组有效元素的行数是，i行0列，二维数组的列数是i行1列，二维数组有效元素值是i行2列 twoDimensionArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2]; } } return twoDimensionArray; } return null; } }
三、总结和思考
1.可以不记录原始数组的行数和列数吗？
我们发现即使不记录原始数组的行数和列数，我们依然可以实现将原始数组的所有有效信息进行保存并还原，但是若是我们不清楚原始数据的行数和列数，是做不到将原始数组百分百还原的，我们能还原的只是有效数据，所以这是不可取的，显然不记录原始数组的行数和列数是不行的。
2.学习稀疏数组收获了什么
学习稀疏数组，笔者感觉主要的收获就是一种思想，化繁为简的思想，摒弃垃圾数据，只保留有效数据的细想。然后存储这部分有效信息，在需要时将这些信息返显，甚至天马星空的来说，我们都可以用稀疏数组实现加密，因为别人并不清楚这是个稀疏数组，也不清楚你这里存了啥，当然了如果将稀疏数组应用于加密，我们就不应该考虑空间和时间的性能消耗了，因为他的初衷是加密而不是节约空间的存储了。
