稀疏数组
学习就了如果累了,就休息一下,不要疲劳学习,效果不好,要永远对知识充满渴望
/*
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 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
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
*/
形如上面的一个11*11的数组,仅两位值不为0,其余值均为0,存储为数组占用空间,为了压缩空间,节约成本,可以将其压缩为稀疏数组
稀疏数组:
当一个数组中大部分元素为0,或者为同一值,就可以使用稀疏数组来保存该数组
稀疏数组的处理方式
1.记录数组一共有几行几列,有多少个不同值
2.把具有不同值的元素行列及值记录在一个小规模的数组中,从而缩小程序的规模
原始数组及稀疏数组
/*
原始数组 稀疏数组
行 列 值
0 0 0 0 0 0 0 0 0 0 0 [0] 11 11 2
0 0 1 0 0 0 0 0 0 0 0 [1] 1 2 1
0 0 0 2 0 0 0 0 0 0 0 [2] 2 3 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 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
*/
原始数组转稀疏数组
public static int[][] normalToSparse(int[][] normal) {
int sum = 0;
for (int i = 0; i < normal.length; i++) {
for (int j = 0; j < normal[0].length; j++) {
if (normal[i][j] != 0) {
sum++;
}
}
}
int[][] sparse = new int[sum + 1][3];
sparse[0][0] = normal.length;
sparse[0][1] = normal[0].length;
sparse[0][2] = sum;
int count = 0;
for (int i = 0; i < normal.length; i++) {
for (int j = 0; j < normal[0].length; j++) {
if (normal[i][j] != 0) {
count++;
sparse[count][0] = i;
sparse[count][1] = j;
sparse[count][2] = normal[i][j];
}
}
}
for (int i = 0; i < sparse.length; i++) {
System.out.println(sparse[i][0] + " " + sparse[i][1] + " " + sparse[i][2]);
}
return sparse;
}
稀疏数组转原始数组
public static int[][] sparseToNormal(int[][] sparse) {
int[][] normal = new int[sparse[0][0]][sparse[0][1]];
for (int i = 1; i <= sparse[0][2]; i++) {
normal[sparse[i][0]][sparse[i][1]] = sparse[i][2];
}
for (int i = 0; i < normal.length; i++) {
System.out.println(Arrays.toString(normal[i]));
}
return normal;
}