数据结构之数组与稀疏数组
背景
编写五子棋程序保存棋盘
我们如何保存整个棋盘呢？最简单也是最容易想到的就是用一个二维数组来表示
-
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);
}
/**
* 创建二维数组
* @return
*/
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;
}
/**
* 打印数组
* @param 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("-------------------------");
}
/**
* 二维数组转稀疏数组
* @param chessArr
* @return
*/
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;
}
/**
* 稀疏数组转二维数组
* @param sparseArr
* @return
*/
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;
}
核心代码
/**
* 二维数组转稀疏数组
* @param chessArr
* @return
*/
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;
}
运行结果:
稀疏数组转二维数组
思路:
-
先读取稀疏数组的第一行数据，创建出原始数组 -
读取稀疏数组除第一行棋盘数据的数据赋值给二维数组
/**
* 稀疏数组转二维数组
* @param sparseArr
* @return
*/
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;
}
运行结果:
原文始发于微信公众号（小奏技术）：数据结构之稀疏数组
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/30027.html
