稀疏数组
什么是稀疏数组？
先看看百度百科上关于 稀疏矩阵 的定义吧：
在矩阵中，若数值为0的元素数目远远多于非0元素的数目，并且非0元素分布没有规律时，则称该矩阵为稀疏矩阵；
OK，讲讲我的理解，直接举个例子吧，11*11的棋盘，如果现在只有 第2行第3列为黑色旗子，第3行第4列为白色旗子，让我们将这个棋盘用代码表示出来，怎么办？
二维数组呗。定义一个 a[11][11] ，然后无旗子用0表示，黑色用1表示，白色用2表示，即 arr[1][2] = 1 arr[2][3] = 2 ，这样不就OK了。可以，我们在main方法中用代码表示出来，并把它打印：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int[][] arr = new int[11][11];
arr[1][2] = 1;
arr[2][3] = 2;
System.out.println("-----------源数组-----------");
for (int[] ints : arr) {
for (int item : ints) {
System.out.printf("%d\t",item);
}
System.out.println();
}
|
执行了如下图所示：
这样可以，但是这样有点浪费空间呀，因为有太多0了，我们没必要让这些0占用这么多空间。
如之奈何？我们就默认为0，只把这些非0的表示出来，岂不美哉？
好的，什么意思？行、列、对应数值，这三个属性对应一个非0数。这样我们用两列三行，就能表示这个大的源数组，但是不要忘了，源数组还有行列个数，我们直接把它们定义在第0行，对应行 列 属性，还有一个 数值 属性怎么办？填入非0的个数呗。
综上所述，我们只用一个 3 *3的二维数组就能表示 11 *11的源数组，那么这个3 *3的二维数组就是稀疏数组。
下面我们将定义两个方法，分别进行源数组和系数数组的转换，不难的。
源数组转换成稀疏数组
源数组我们刚刚已经写出来了，怎么将它转换成稀疏数组呢？
我们动动我们的大脑，首先要得到行数、列数、非0个数，将这三个数填入到第0行，然后再遍历源数组，将那些非0的数，再填入稀疏数组就成了。
思想大致就是这样，我们定义一个静态方法完成这个方法，如下所示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
public static int[][] toSparseArray(int[][] arr){
int row = arr.length;
int column = arr[0].length;
int sum = 0;
for (int[] ints : arr) {
for (int item : ints) {
if(item!=0)
sum++;
}
}
int[][] arrRes = new int[++sum][3];
arrRes[0][0] = row;
arrRes[0][1] = column;
arrRes[0][2] = sum;
int count = 1;
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if(arr[i][j]!=0){
arrRes[count][0] = i;
arrRes[count][1] = j;
arrRes[count][2] = arr[i][j];
count++;
}
}
}
return arrRes;
}
|
这个不难理解吧，OK，在main方法后面进行测试一下：
1
2
3
4
5
6
7
8
9
10
|
int[][] arrRes = toSparseArray(arr);
System.out.println("-----------稀疏数组-----------");
for (int[] ints : arrRes) {
for (int item : ints) {
System.out.printf("%d\t",item);
}
System.out.println();
}
|
输出结果：
美哉美哉！
稀疏数组转换成源数组
上面如果会了的话，这个应该闭着眼都能整出来，这个比上面那个简单多了。
稀疏数组第0行行数、列数都给我们了，我们就能new出来源数组了。
然后从第1行遍历稀疏数组的行，根据每一行的行、列、对应数值，这三个属性，分分钟就把它们填入到源数组了。OK，代码直接走起，还是静态方法：
1
2
3
4
5
6
7
8
9
10
11
|
public static int[][] toSourceArr(int[][] arr){
int row = arr[0][0];
int column = arr[0][1];
int count = arr[0][2];
int[][] arrRes = new int[row][column];
for (int i = 1; i < arr.length; i++) {
arrRes[arr[i][0]][arr[i][1]] = arr[i][2];
}
return arrRes;
}
|
还是在main方法中进行测试：
1
2
3
4
5
6
7
8
9
10
|
int[][] sourceArr = toSourceArr(arrRes);
System.out.println("-----------源数组-----------");
for (int[] ints : sourceArr) {
for (int item : ints) {
System.out.printf("%d\t",item);
}
System.out.println();
}
|
输出结果如下：
