记录生活中的点点滴滴

0%

稀疏数组

稀疏数组

什么是稀疏数组?

先看看百度百科上关于 稀疏矩阵 的定义吧:

在矩阵中,若数值为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;//列数
//先遍历得到非0的个数
int sum = 0;//非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;
//再遍历源数组,把非0的数填入到稀疏数组中
int count = 1;//计数器,要初始为1
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if(arr[i][j]!=0){
arrRes[count][0] = i;//行数为i
arrRes[count][1] = j;//列数为j
arrRes[count][2] = arr[i][j];//数值为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];//非0个数
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();
}

输出结果如下: