稀疏数组基本概念
在我们存储有大量重复元素值的二维数组时,如果使用一般的二维数组可能会有大量重复元素,这样就会浪费空间,例如
| 0 | 0 | 0 | 0 |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 2 |
| 0 | 0 | 0 | 0 |
实际只有两个有效数据,却存储了四行四列
稀疏数组表示
- 遍历该数组,记录实际有效数据的个数
- 稀疏数组的第一行表示需要被转换的数组有多少行多少列,有效数据是多少个
- 从第二行开始记录实际有效数据的行，列，以及实际数据
上面的数组就可以表示成
| 4 | 4 | 2 |
|---|---|---|
| 1 | 2 | 1 |
| 2 | 3 | 2 |
实际不管什么二维数组都会转换成 有效数据行+1和三列的数组
代码实现如下
package suanfa;
/**
* 稀疏数组
*/
public class SparseArray {
public static void main(String[] args) {
//初始化数据
int [][]data = new int[4][4];
data[1][2] = 1;
data[2][3] = 2;
printArr(data);
int sparseArr[][] = transform(data,0);
printArr(sparseArr);
}
/**
* 转换稀疏数组
* @param data 原数组
* @param repeat 重复元素
* @return 转换后的稀疏数组
*/
public static int[][] transform(int[][] data,int repeat){
int valid = 0;//有效数据
int rowNum = data.length;//行
int colNum = data[0].length;//列
/**计算有效数据 */
for (int[] datum : data) {
for (int i : datum) {
if(i != repeat) {
++valid;
}
}
}
/**稀疏数组赋值*/
int sparse [][] = new int[valid+1][3];
sparse[0][0] = rowNum;
sparse[0][1] = colNum;
sparse[0][2] = valid;
int sparseCurrentrow = 0;//稀疏数组当前存储到的行
for(int i = 0;i<data.length;++i){
for(int j = 0;j<data[i].length;++j){
if(data[i][j] != repeat){
sparse[++sparseCurrentrow][0] = i;
sparse[sparseCurrentrow][1] = j;
sparse[sparseCurrentrow][2] = data[i][j];
}
}
}
return sparse;
}
/**
* 输出二维数组
* @param data
*/
public static void printArr(int data[][]){
for(int i = 0;i<data.length;++i){
for(int j = 0;j<data[i].length;++j){
System.out.printf("%d\t",data[i][j]);
}
System.out.println();
}
}
}
运行结果如下
深度截图_选择区域_20191223164839.png
运用场景
例如,在保存游戏进度时,用二维数组来表示数据,就可以把数据转换成稀疏数组在保存到本地,例如五子棋盘中途保存等
