稀疏数组
一、 稀疏数组介绍
使用场景 ： 当一个二维数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组
举个例子 ：
有下面这样一个11X11的二维数组，很多元素都是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 5 0 0 0 0 0 0 0
0 0 0 0 7 3 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
我们可以简化成下面这样， 第一行的元素 记录 原始数组的 行数，列数，非零元素个数 ；第二行开始记录第一个非零元素在原始数据的位置和值是什么，第三行开始记录第二个非零元素在原始数组的位置和值是什么，以此类推
11 11 4
3 3 5
4 4 7
4 5 3
5 5 1
稀疏数组第一行 ： 第一个元素标示 原始数据有11行，第二个元素标示 原始数组有 11列， 第三个元素标示 原始数组共有多少个非零元素
稀疏数组第二行 ：第一个元素标示 原始数组第一个非零元素所在的行， 第二个元素标示 原始数组第一个非零元素所在的列， 第三个元素标示，原始数组第一个非零元素的具体值是多少
依次类推。。。
这样是不是即简化了数组，又节省了空间
二、转换思路和代码实现
原始二维数组转换为稀疏数组
1、遍历原始二维数组得到非0元素的个数，我们就可以得到稀疏数组的行数： 为原始二维数组的非零个数+1，稀疏数组的列是固定的3列，这样我们就拿到了稀疏数组；
2、遍历原理二维数组，依次得到非零元素，把原始二维数组的坐标和具体值赋值给稀疏数组即可
稀疏数组还原原始二维数组
1、从稀疏数组的第一行元素即可得到原始二维数组的行列数
2、遍历稀疏数组，把行列和值付给原始二维数组即可
具体代码如下 ：
package arr;
public class MyArrayTest {
public static void main(String[] args) {
//原始的二维数组
int[][] matrixArray = new int[11][11];
matrixArray[5][5] = 1;
matrixArray[4][4] = 2;
matrixArray[3][3] = 1;
matrixArray[4][5] = 2;
//拿到非0个数，并打印数组
int sum = getNonZeroElementNumberAndPrint(matrixArray);
System.out.println("二维数组中非0元素个数 ： "+sum);
//稀疏数组 初始化
int[][] sparseArray = new int[sum + 1][3];
sparseArray[0][0] = 11;
sparseArray[0][1] = 11;
sparseArray[0][2] = sum;
//二维数组转稀疏数组
int count = 1;//稀疏数组行规律是原始二维数组每个元素一行，所以是递增的
for (int i = 0; i < matrixArray.length; i ++){
for (int j = 0; j < matrixArray[i].length; j++){
if(matrixArray[i][j] != 0){
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = matrixArray[i][j];
count ++;
}
}
}
System.out.println("转换之后的二维数组 ： ");
//打印二维数组
getNonZeroElementNumberAndPrint(sparseArray);
//稀疏数组还原二维数组
int [][] orginMatrixArray = restoreArrayFromSparseArray(sparseArray);
System.out.println("还原之后的二维数组 ： ");
//打印还原之后的二维数组
getNonZeroElementNumberAndPrint(orginMatrixArray);
}
/**
* 稀疏数组还原二维数组
*/
private static int[][] restoreArrayFromSparseArray(int[][] sparseArray) {
int[][] orginArray = new int[sparseArray[0][0]][sparseArray[0][1]];
for (int i = 1; i < sparseArray.length; i ++){
orginArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
return orginArray;
}
/**
* 二维数组打印
*/
private static int getNonZeroElementNumberAndPrint(int[][] array){
int sum = 0;
for (int[] arr : array){
for (int a : arr){
if(a != 0){
sum ++;
}
System.out.print(a + "\t");
}
System.out.println();
}
return sum;
}
}
三、应用场景
现在想到的应用场景不是特别多
1、如棋盘，地图等数据存储
2、对矩阵数据压缩