稀疏数组

在遇到棋盘或者地图等问题时，常常需要构造一个二维数组。以棋盘为例，需要大量的0（或者其他相同的默认数值）来组成棋盘的基本结构，而数组中非0值的位置却很少。为了节省空间，可以用稀疏数组来存储相应信息。

稀疏数组是一个3列的二维数组，稀疏数组的第一行总是存储原来二维数组的行列和有效值的信息。分别是：

1. 第一行第一列存原来二维数组的总行数
2. 第一行第二列存原来二维数组的总列数
3. 第一行第三列存原来二维数组的非0（有效）值的总个数

从稀疏数组的第二行往下，存放原来二维数组的有效信息，每一个有效值的信息在稀疏数组中的存放形式如下：

1. 第1列存放某一个有效值出现的行
2. 第2列存放那一个有效值出现的列
3. 第3列存放那个有效的值

原来一个9*9的大数组，在使用稀疏数组后，变成一个5*3的小数组，节约了空间。图上能反应出稀疏数组与原来二维数组的对应关系。

• 二维数组-->稀疏数组

通过遍历原来的二维数组可以找到每一个有效值的信息，然后赋值给稀疏数组。

java代码实现：

 1  public static int[][] twoToSparse(int[][] arr) {
 2         //将二维数组变成稀疏数组
 3         int sum = 0; //记录原数组有几个非0的值，用于确定稀疏数组的行数
 4         int columnNum = 0; //记录原数组的列数
 5         for (int[] ints : arr) {
 6             columnNum = 域名th; //获取列数
 7             for (int anInt : ints) {
 8                 if (anInt != 0) {
 9                     sum++;
10                 }
11             }
12         }
13         int[][] sparseArr = new int[sum + 1][3];
14         sparseArr[0][0] = 域名th;
15         sparseArr[0][1] = columnNum;
16         sparseArr[0][2] = sum;
17         int count = 0;//纪录出现的值是第几个
18         for (int i = 0; i < 域名th; i++) {  //遍历原来的二维数组，找到非0处的值，将信息赋值给稀疏数组
19             for (int j = 0; j < columnNum; j++) {
20                 if (arr[i][j] != 0) {
21                     count++; //第几个出现就放在第几行（第0行存放原数组的 总行数，总列数，总非0的值的数量）
22                     sparseArr[count][0] = i; //第一列存放行数
23                     sparseArr[count][1] = j; //第二列存放列数
24                     sparseArr[count][2] = arr[i][j]; //第三列存放具体的值
25                 }
26             }
27         }
28         return sparseArr;
29     }

• 稀疏数组-->二维数组

通过遍历稀疏数组的信息，很快就能获得二维数组的信息，然后将原来需要的二维数组恢复。

java代码实现：

 1     public static int[][] sparseToTwo(int[][] sparseArr) {
 2         //将稀疏数组恢复成二维数组
 3         int[][] arr = new int[sparseArr[0][0]][sparseArr[0][1]]; //利用稀疏数组中第一行的总行列数信息，创建一个二维数组
 4         if (sparseArr[0][2] == 0) {
 5             return arr; //没有有效值，直接返回只有默认值的数组，这里默认值是0，不需要进行另外的赋值操作
 6         } else {
 7             for (int i = 1; i < 域名th; i++) {
 8                 arr[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];  //遍历稀疏数组，读取行，列，值信息，赋给二维数组
 9 
10             }
11             return arr;
12         }
13     }