背景稀疏数组编码实现
二维数组转稀疏数组稀疏数组转二维数组
背景这里是weihubeats,觉得文章不错可以关注公众号小奏技术，文章首发。拒绝营销号，拒绝标题党
编写五子棋程序保存棋盘
我们如何保存整个棋盘呢？最简单也是最容易想到的就是用一个二维数组来表示
0：表示没有棋子1：表示黑棋2：表示白旗
数组大小为整个棋盘的x、y值的最大值 int[x][y]
可以看到通常我们的棋子并不总是存满整个棋盘的，但是我们总是需要创建 一个x*y的数组，非常浪费空间。如何优化呢
稀疏数组先来看看稀疏数组的应用场景:
当一个数组中 大部分元素为 0（或是同一个值） 时，可以使用 稀疏数组 来保存该数组
具体处理方式:
- 记录数组共有几行几列，即max(x)轴，max(y)轴,有多少个不同的值把不同值的元素的行列及值记录在一个小规模的数组中，从而压缩空间
例子:
可以看到我们有这么一个二维数组int[12][4],其中有值的数组下标及值分别为
int[0][2] = 10
int[0][3]= 14
int[3][2] = 15
int[8][1] = 6
int[9][0] = 7
int[11][1] = 88
那么压缩成稀疏数组为
这里需要注意稀疏数组的第一个元素的构成永远是原二维数组的 最大行、最大列、以及所有值的sum
可以看到原先数组大小为: 12 * 4 = 48
使用稀疏数组后的大小为: 7*3 = 21
编码实现 二维数组转稀疏数组大致思路:
- 遍历原始的二维数组，得到有效数据的个数 sum根据sum创建稀疏数组 sparseArr int[sum+1][3]将二维数组的有效数据存入到稀疏数组
代码实现
完整源码:
public static void main(String[] args) {
// 构建二维数组
int[][] chessArr = createChessArr();
// 打印二维数组
printChessArray(chessArr);
// 二维数组转稀疏数组
int[][] chessArr1 = chessToSparse(chessArr);
printChessArray(chessArr1);
// 稀疏数组转二维数组
int[][] chessArr2 = sparseToChess(chessArr1);
printChessArray(chessArr2);
}
private static int[][] createChessArr() {
int[][] chessArr = new int[12][4];
chessArr[0][2] = 10;
chessArr[0][3] = 14;
chessArr[3][2] = 15;
chessArr[8][1] = 6;
chessArr[9][0] = 7;
chessArr[11][1] = 88;
return chessArr;
}
private static void printChessArray(int[][] chessArr) {
for (int[] ints : chessArr) {
for (int anInt : ints) {
System.out.printf("%-2dt", anInt);
}
System.out.println();
}
System.out.println("-------------------------");
}
private static int[][] chessToSparse(int[][] chessArr) {
// 遍历二维数组得到非0元素个数
int sum = 0;
for (int[] ints : chessArr) {
for (int anInt : ints) {
if (anInt != 0) {
sum++;
}
}
}
// 构建稀疏数组 构建的 sum + 1 是为了用来保存第一个元素为原元素x、y轴的最大值
int[][] sparseArr = new int[sum + 1][3];
// 给稀疏数组赋值(将二维数组非0元素存入稀疏数组中)
int chessRow = chessArr.length; // 行 = 棋盘大小
int chessCol = 0; // Lie
// 当前是第几个非0的数据
int count = 0;
for (int i = 0; i < chessArr.length; i++) {
int[] rows = chessArr[i];
if (chessCol == 0) {
chessCol = rows.length;
}
for (int j = 0; j < rows.length; j++) {
int chess = rows[j];
if (chess == 0) {
continue;
}
count++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chess;
}
}
// 填充第一行的棋盘大小和有效数据
sparseArr[0][0] = chessRow;
sparseArr[0][1] = chessCol;
sparseArr[0][2] = sum;
return sparseArr;
}
private static int[][] sparseToChess(int[][] sparseArr) {
// 1. 创建二维数组
int chessRow = sparseArr[0][0]; // 行
int chessCol = sparseArr[0][1]; // 列
int[][] chessArr = new int[chessRow][chessCol];
// 非0数据填充 排除第一行的棋盘大小记录
for (int i = 1; i < sparseArr.length; i++) {
int[] rows = sparseArr[i];
chessArr[rows[0]][rows[1]] = rows[2];
}
return chessArr;
}
核心代码
private static int[][] chessToSparse(int[][] chessArr) {
// 遍历二维数组得到非0元素个数
int sum = 0;
for (int[] ints : chessArr) {
for (int anInt : ints) {
if (anInt != 0) {
sum++;
}
}
}
// 构建稀疏数组 构建的 sum + 1 是为了用来保存第一个元素为原元素x、y轴的最大值
int[][] sparseArr = new int[sum + 1][3];
// 给稀疏数组赋值(将二维数组非0元素存入稀疏数组中)
int chessRow = chessArr.length; // 行 = 棋盘大小
int chessCol = 0; // Lie
// 当前是第几个非0的数据
int count = 0;
for (int i = 0; i < chessArr.length; i++) {
int[] rows = chessArr[i];
if (chessCol == 0) {
chessCol = rows.length;
}
for (int j = 0; j < rows.length; j++) {
int chess = rows[j];
if (chess == 0) {
continue;
}
count++;
sparseArr[count][0] = i;
sparseArr[count][1] = j;
sparseArr[count][2] = chess;
}
}
// 填充第一行的棋盘大小和有效数据
sparseArr[0][0] = chessRow;
sparseArr[0][1] = chessCol;
sparseArr[0][2] = sum;
return sparseArr;
}
运行结果:
稀疏数组转二维数组思路:
- 先读取稀疏数组的第一行数据，创建出原始数组读取稀疏数组除第一行棋盘数据的数据赋值给二维数组
private static int[][] sparseToChess(int[][] sparseArr) {
// 1. 创建二维数组
int chessRow = sparseArr[0][0]; // 行
int chessCol = sparseArr[0][1]; // 列
int[][] chessArr = new int[chessRow][chessCol];
// 非0数据填充 排除第一行的棋盘大小记录
for (int i = 1; i < sparseArr.length; i++) {
int[] rows = sparseArr[i];
chessArr[rows[0]][rows[1]] = rows[2];
}
return chessArr;
}
运行结果:
