稀疏数组 - 只存储有效元素的位置信息与有效值
1.1 代码实现
背景： 做个五子棋棋盘，整个棋盘由二维数组的0( 无棋 )、1( 白方棋 )、2( 黑方棋)元素进行映射棋盘，如果我想把当前状态的棋盘信息序列化到硬盘上，存储了大量的无用信息0，故可用稀疏数组来进行缩小存储的信息*
实现步骤
1、 记录真正数组的行、列、以及有效元素的个数；
2、 把每个有效元素在真正数组的【位置(行号、列号)与有效值】用单维数组进行封装；
代码实现 - 真实数组 → 稀疏数组
public static int[][] sparseArray(int[][] array) {
// 1. 稀疏数组的每个子元素数组 先存储在 数组容器中
ArrayList<int[]> validArrayList = new ArrayList<int[]>();
// 2. 容器中的第一个元素存储 真实数组(形参array)的 行数、列数、有效元素个数三个指标
int[] indexNum = {
array.length, 0, 0 };
validArrayList.add(indexNum);
// 3. 定义初始化 真实数组中的 有效个数、以及 最大列数
int validCount = 0;
int maxColumn = 0;
// 4. 遍历真实数组 -- 检索有效的元素，并将有效元素 在 真实数组的 行数、列数、有效值 以数组的元素封装存储在 数组容器中
for (int i = 0; i < array.length; i++) {
// 4.1 寻找最大的列数
int column = array[i].length;
if (maxColumn < column) {
maxColumn = column;
}
for (int j = 0; j < column; j++) {
if (array[i][j] != 0) {
int[] valid = new int[3];
changArr(valid, i, j, array[i][j]);
validArrayList.add(valid);
validCount++;
}
}
}
validArrayList.get(0)[2] = validCount;
validArrayList.get(0)[1] = maxColumn;
// 5. 将 数组容器 转为 稀疏二维数组
int[][] validArray = validArrayList.toArray(new int[validCount+1][3]);
// 6. 返回 稀疏二维数组
return validArray;
}
/**
* @Description 对在真实数组的有效的元素，的行、列、值进行封装为数组
*/
public static void changArr(int[] valid, int row, int column, int value) {
valid[0] = row;
valid[1] = column;
valid[2] = value;
}
代码实现 - 稀疏数组 → 真实数组
public static int[][] realArray(int[][] sparseArray) {
// 1. 稀疏数组的第一个数组元素，存储的是 真实数组的信息
int row = sparseArray[0][0];
int column = sparseArray[0][1];
int validCount = sparseArray[0][2];
// 2. 由 1的信息 初始化一个 真实数组
int [][] realArr = new int[row][column];
// 3. 还原真实数组的 有效值
for(int i = 1; i <= validCount; i++) {
int validRow = sparseArray[i][0];
int validColumn = sparseArray[i][1];
realArr[validRow][validColumn] = sparseArray[i][2];
}
// 4. 返回真实数组
return realArr;
}
1.2 测试 - 代码
public static void main(String[] args) {
// 1. 初始化原数组 -- 并给原数组两个有效值
int[][] numbers = new int[8][9];
numbers[7][5] = 23;
numbers[6][4] = 60;
// 2. 打印真实数组
System.out.println("原数组(真实数组)：----------------------------");
for (int row = 0; row < numbers.length; row++) {
for (int column = 0; column < numbers[row].length; column++) {
System.out.printf("%d\t", numbers[row][column]);
}
System.out.println("");
}
// 3. 打印 真实数组转为稀疏数组
System.out.println("\n稀疏数组-------------------------");
int[][] sparseArr = sparseArray(numbers);
for(int i = 0; i<sparseArr.length; i++) {
System.out.printf("%d\t%d\t%d\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][1] );
}
//4. 打印 稀疏数组 转为 真实数组
System.out.println("\n稀疏转真实数组--------------------------");
int[][] realArr = realArray(sparseArr);
for (int row = 0; row < realArr.length; row++) {
for (int column = 0; column < realArr[row].length; column++) {
System.out.printf("%d\t", numbers[row][column]);
}
System.out.println("");
}
}
运行结果
