稀疏数组

概念介绍

　　有同学想了解稀疏数组，今天它来了！它能节约空间，让你计算少花时间!它是大型科学工程计算领域常客，被誉为“矩阵压缩一号”！

　　在介绍稀疏数组前，我们先来看下这个二维数组。

，对于这个二维数组，我们真正关心的数据有哪些呢？

答案是：1.这是一个3行4列的二维数组。2.在下标为（1，2）的位置，记录的数字是1；在下标为（2，3）的位置，记录的数字是2。

大家发现没有，我们这个二维数组中，除了1和2之外，其余的都是0，这些0我们并不关心，但是它占用了大量的空间，有没有更好的方式来描述这个二维数组呢？稀疏数组能帮我们解决这个问题。

第一步：我们先把重要的信息拿出来， 3行4列，而我们关心的值的个数为2个，那么我们就这么记：

，3表示总行数，4表示总列数，2表示真正有效数字的个数。

第二步：把那两个我们关心的值的坐标给拿出来，那么我们可以这样记：

，这时候，行列表示坐标的位置，而值为该坐标轴上的数字。将第一步和第二步一合并，我们可以得到：

　，这就是稀疏数组，如果来个需求，在1个1000X1000的数组上表示上述两点，那么最后这种方式，是不是能节省大量的空间呢？

　　所以什么情况下我们该用稀疏数组呢？当一个数组中大部分元素为０，或者为同一个值时，可以使用稀疏数组来保存该数组。

代码实现

　　接下来，咱们就用代码去实现将二维数组转为稀疏数组以及将稀疏数组还原为二维数组。在开始写代码前，一定要先明确思路，我们的目的是什么？为了达到目的，我们得分几步完成？有了思路，才去写代码。

二维数组转为稀疏数组：

　　为了将二维数组转为稀疏数组，我们可以通过以下三步来完成：

　　第一步：先遍历二维数组,得到有效数字的个数。

　　第二步：根据二维数组及有效数字的个数创建稀疏数组。

　　第三步：为稀疏数组赋值。

　　代码实现如下：

1     public static int[][] twoDimensionalArrToSparseArr(int[][] twoDimensionalArr){
2         // 第一步：先遍历二维数组,得到有效数字的个数
3         int sum = getTwoDimensionalArrEffectiveNumber(twoDimensionalArr);
4         // 第二步：根据二维数组及有效数字的个数创建稀疏数组
5         int [][] sparseArr = createSparseArr(twoDimensionalArr,sum);
6         // 第三步：为稀疏数组赋值
7         assignForSparseArr(twoDimensionalArr,sparseArr);
8         return sparseArr;
9     }

　　getTwoDimensionalArrEffectiveNumber(twoDimensionalArr)的具体实现如下：

 1     private static int getTwoDimensionalArrEffectiveNumber(int[][] twoDimensionalArr){
 2         int sum = 0;
 3         for (int i = 0; i < twoDimensionalArr.length; i++) {
 4             for (int j = 0; j < twoDimensionalArr[i].length; j++) {
 5                 if (twoDimensionalArr[i][j] != 0) {
 6                     sum++;
 7                 }
 8             }
 9         }
10         return sum;
11     }

　　createSparseArr(twoDimensionalArr,sum)的具体实现如下：

1     private static int[][] createSparseArr(int[][] twoDimensionalArr,int sum){
2         int sparseArr[][] = new int[sum + 1][3];
3         sparseArr[0][0] = twoDimensionalArr.length;
4         sparseArr[0][1] = twoDimensionalArr[0].length;
5         sparseArr[0][2] = sum;
6         return sparseArr;
7     }

　　assignForSparseArr(twoDimensionalArr,sparseArr)的具体实现如下：

 1     private static void assignForSparseArr(int[][] twoDimensionalArr,int [][] sparseArr){
 2         // count用于记录是第几个非0数据
 3         int count = 0;
 4         for (int i = 0; i < twoDimensionalArr.length;i++) {
 5             for (int j = 0; j < twoDimensionalArr[i].length; j++) {
 6                 if(count == sparseArr[0][2]){
 7                     return ;
 8                 }
 9                 if (twoDimensionalArr[i][j] != 0) {
10                     count++;
11                     sparseArr[count][0] = i;
12                     sparseArr[count][1] = j;
13                     sparseArr[count][2] = twoDimensionalArr[i][j];
14                 }
15             }
16         }
17     }

稀疏数组转换为二维数组：

　　为了将稀疏数组转换为二维数组，我们可以通过以下两步来完成：

　　第一步：根据稀疏数组创建二维数组。

　　第二步：为二维数组赋值。

　　代码实现如下：

1     public static int[][] sparseArrToTwoDimensionalArr(int[][] sparseArr){
2         // 第一步：根据稀疏数组创建二维数组
3         int twoDimensionalArr[][] = createTwoDimensionalArr(sparseArr);
4         // 第二步：为二维数组赋值
5         assignForTwoDimensionalArr(sparseArr,twoDimensionalArr);
6         return twoDimensionalArr;
7     }

　　createTwoDimensionalArr(sparseArr)的具体实现如下：

1     private static int[][] createTwoDimensionalArr(int[][] sparseArr){
2         return new int[sparseArr[0][0]][sparseArr[0][1]];
3     }

　　assignForTwoDimensionalArr(sparseArr,twoDimensionalArr)的具体实现如下：

1     private static void assignForTwoDimensionalArr(int[][] sparseArr,int[][] twoDimensionalArr){
2         for(int i = 1; i < sparseArr.length; i++) {
3             twoDimensionalArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
4         }
5     }

　　至此，代码编写完成，Git地址：https://github.com/HollowCup/algorithms-and-data-structure，具体实现位于data-structure工程下的sparseArr目录，如果发现不足之处，请联系我进行更改，十分感谢！关注我，为你揭秘更多数据结构!