1、应用场景
-
五子棋盘的存储
-
上面这个棋盘如果使用二维数组存储（1存储黑色棋子，2存储蓝色棋子），如下所示：
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]-
可以看到会存储许多无意义的0，浪费空间
-
-
如果使用稀疏矩阵存储，结果如下
[[13, 13, 3],
[2, 3, 1],
[3, 4, 2],
[4, 6, 1]]
-
2、概念
-
记录一个大部分元素都为0，或者为同一个值的数组
-
存储值的方法：
列数恒定为3，行数随二维数组中非零数组元素个数而定
0 1 2
0 二维数组行数 二维数组列数 非零元素个数
1 第一个非零元素在二维数组中的行索引 第一个非零元素在二维数组中的列索引 第一个非零元素的值
2 第二个非零元素在二维数组中的行索引 第二个非零元素在二维数组中的列索引 第二个非零元素的值
...
n 第n-1个非零元素在二维数组中的行索引 第n-1个非零元素在二维数组中的列索引 第n-1个非零元素的值
3、二维数组和稀疏数组的相互转换
public class SparseArray {
public static void main(String[] args) {
// 二维数组
int[][] arrays = new int[11][11];
arrays[1][2] = 1;
arrays[2][3] = 2;
arrays[5][6] = 1;
/**
* 将二维数组转换为稀疏数组
* 1、遍历二维数组，得到非零数据的个数，用以确定稀疏矩阵的行列值
* 2、创建稀疏数组
* 确定稀疏矩阵第一行数据
* 遍历二维数组，确定稀疏矩阵的其他数据
*/
int sum = 0;
for (int i = 0; i < arrays.length; i++) {
for (int j = 0; j < arrays[i].length; j++) {
if (arrays[i][j] != 0){
sum ++;
}
}
}
int[][] sparseArray = new int[sum + 1][3];
// 第一行数据
sparseArray[0][0] = arrays.length;
sparseArray[0][1] = arrays[0].length;
sparseArray[0][2] = sum;
// 遍历二维数组，存放非零数据
int count = 0; //记录当前是第几个非零数据
for (int i = 0; i < arrays.length; i++) {
for (int j = 0; j < arrays[i].length; j++) {
if (arrays[i][j] != 0){
count ++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = arrays[i][j];
}
}
}
/**
* 将稀疏数组转换为二维数组
* 1、得到二维数组的行列
* 2、遍历稀疏矩阵，得到二维数组的非零元素
*/
int[][] twoArray = new int[sparseArray[0][0]][sparseArray[0][1]];
for (int i = 1; i < sparseArray.length; i++) {
twoArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
}
}