稀疏数组
什么是稀疏数组?
先看看百度百科上关于 稀疏矩阵
的定义吧:
在矩阵中,若数值为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(); }
|
输出结果如下:
