稀疏数组基本概念:
稀疏数组应用场景:
当一个数组大部分的元素为"0",或者为同一个值的数组时,可以使用稀疏数组来保存该数组
处理方法:
1>记录数组一共有几行几列,有多少不同的值
2>把具有不同值的元素行列及值记录在一个小规模数组中,从而缩小程序规模
row col val
[0] 总行 总列 有效数量
[1] 第一个数据行 第一个数据列 第一个数据值
[2] 第二个数据行 第二个数据列 第二个数据值
二维数组==>稀疏数组思路:
1>遍历原始二维数组,得到有效数字的个数:sum (sum为变量名可自定义)
2>根据sum创建稀疏数组sparseArray int[sum+1][3]
3>再次遍历原始数组将二维数组有效数据存入稀疏数组
代码实现:
int[][] array01 = new int [11][11];
array01[0][1] = 1;
array01[1][2] = 2;
Integer sum = 0;
for(int i = 0; i<array01.length;i++) {
for(int j = 0;j<array01[i].length;j++) {
if(array01[i][j]!=0) {
sum++;
}
}
}
int [][] array02 = new int[sum+1][3];
array02[0][0] = array01.length;
array02[0][1] = array01[0].length;
array02[0][2] = sum;
Integer sum2 = 0;
for(int i = 0; i<array01.length;i++) {
for(int j = 0;j<array01[i].length;j++) {
if(array01[i][j]!=0) {
sum2++;
array02[sum2][0] = i;
array02[sum2][1] = j;
array02[sum2][2] = array01[i][j];
}
}
}
稀疏数组==>二维数组思路
1>先读取稀疏数组第一行,根据第一行数据创建原始的二维数组
2>在读取稀疏数组后几行的数据,并赋给原始的二维数组
代码实现
int [][]array03 = new int[array02[0][0]][array02[0][1]];
for(int i = 1;i<array02.length;i++) {
array03[array02[i][0]][array02[i][1]] = array02[i][2];
}