搞清楚稀疏数组之前，先得知道什么是二维数组
二维数组
二维数组相当于一维数组里面存了些一维数组
int[] a={1,2}；
int[] b={3,4};
int[][] ab={a,b}; //里面放a，b数组
内存中位置.png
稀疏数组
稀疏数组.png
可以看到图中 只有几个是有效数字 其他是无效的，很占空间
所以我们可以通过压缩的方式，将数组变小
具体规则：
- 首行： 这个数组有 几行几列 几个有效值（不为0都是有效值）
- 其他行： 第几行 第几列 有效数字是多少
| 行 | 列 | 值 |
|---|---|---|
| 7 | 8 | 3 |
| 3 | 5 | 1 |
| 4 | 5 | 2 |
| 6 | 8 | 4 |
PS：有些博客第一行第一列会写成 0,0
eg.上面的第三行第五列
| 3 | 5 | 1 |
|---|
会写成 对应数组下标的方式
| 2 | 4 | 1 |
|---|
个人觉得我这样方便阅读一点
上代码：
-
压缩
//array[x][y]
public int[][] compressArray(int array[][]){
//记录有几个有效数字
int sum=0;
for (int i = 0; i <array.length ; i++) { //有多少行 x
for (int j = 0; j <array[0].length ; j++) { //有多少列 y 随便算哪行的长度array【i】.lenth 因为列是固定
if(array[i][j]!=0){
sum++;
}
}
}
//初始化压缩后的数组 sum+1是因为首行要放几行几列等有效数据
int[][] endArray=new int[sum+1][3];
//首行信息
endArray[0][0]=array.length;
endArray[0][1]=array[0].length;
endArray[0][2]=sum;
int count=1; //标记给哪行赋值 从第二行开始
//给压缩后的数组赋值
for (int i = 0; i <array.length ; i++) {
for (int j = 0; j <array[0].length ; j++) {
if(array[i][j]!=0){
endArray[count][0]=i+1; //因为数组是从0开始 而我们一般从第一行开始，所以这里+1 方便阅读
endArray[count][1]=j+1;
endArray[count][2]=array[i][j];
count++;
}
}
}
return endArray;
}
-
解压
public int[][] unCompressArray(int[][] array){
//初始化压缩后的数组
int x=array[0][0]; //行
int y=array[0][1];//列
int[][] endArray=new int[x][y];
//从1开始遍历 因为0是首部信息
for (int i = 1; i <array.length ; i++) {
int x2=array[i][0]-1; //行号 不过要减一 因为之前为了阅读方便加了1
int y2=array[i][1]-1; //列号 不过要减一 因为之前为了阅读方便加了1
int num2=array[i][2];
endArray[x2][y2]=num2;
}
return endArray;
}
-
打印
//打印数组
public void printArray(int[][] array){
for (int[] ax: array) {
for (int x:ax) {
System.out.print(x+"\t");
}
System.out.println();
}
}
最终结果：
image.png
应用场景
对重点数据进行记录
围棋：表示黑子或白子（表示子较少的比较好）
地图：在一个坐标系中 表示出哪家商户 xy坐标是多少
*有错误欢迎大家指出*