数据结构与算法-稀疏数组
数据结构与算法-稀疏数组
稀疏数组
1 使用场景
五子棋游戏中
如果要保存游戏进度，可以使用一个二维数组保存棋子位置，结果如图所示：
其中，0代表没有棋子，1代表黑子，2代表白子。
这样的一个15 x 15的棋盘总共要存225个元素，但是有大量的重复数据，比如0，
这样就造成了空间浪费。
我们可以使用一个稀疏数组来存储这个棋盘。
2 思路
一个稀疏数组总共有三列数据。
稀疏数组的第一行数据中：第一列存储原始数组总行数，第二列存储原始数组的总列数，第三列存储总共有多少值。
稀疏数组第一行之后每一行都存储一个原始数据的有效元素的位置和值：第一列存储原始数据的行号，第二列存储原始数据的列号，第三列存储原始数据的值。
上图的棋盘转成稀疏数组之后的结果如图：
在本例中使用上图的稀疏数组只需要存储9个元素，压缩比例很明显。
3 实现
计算给定的一个原始二维数据的总行数，列数和有效元素的个数；
创建一个3列的稀疏数组（其实就是一个普通的二维数组）；
初始化稀疏数组的第一行，第一行第一列为原数组的总行数，第一行第二列为原数组的总列数，第一行第三列为原数组的有效元素个数；
遍历原二维数组，把有效的数据存储到稀疏数组中，没有有效元素占稀疏数组的一行，第一列存储元素的行号，第二列存储元素的列号，第三列存储元素的值；
代码
public class SparseArray { public static void main(String[] args) { //初始化一个棋盘二维数组 int[][] chessArray = initArray(); System.out.println("初始化的原始数组---------------"); print(chessArray); //转为稀疏数组 int[][] sparseArray = toSparseArray(chessArray); System.out.println("稀疏数组---------------"); print(sparseArray); //回复原始数组 int[][] newChessArray = toChessArray(sparseArray); System.out.println("还原的原始数组---------------"); print(newChessArray); } /** * 初始化一个原始二维数据 */ public static int[][] initArray() { int[][] chessArray = new int[15][15]; chessArray[1][3] = 1;//黑子位置 chessArray[2][4] = 2;//白子位置 return chessArray; } /** * 把正常的二维数据转成稀疏数组 * @param chessArray * @return */ public static int[][] toSparseArray(int[][] chessArray) { //遍历获取二维数组中总共有多少个数据 int sum = 0; for (int[] row : chessArray) { for (int val : row) { if (0 != val) { sum++; } } } //创建一个稀疏数组 每行有三个元素，第一个为行号，第二个为列号，第三个为值 int[][] sparesArray = new int[sum+1][3]; //初始化稀疏数组的第一行 int rowNum = chessArray.length; int colNum = chessArray[0].length; //第一行第一列为原二维数组的行数 sparesArray[0][0] = rowNum; //第一行第二列为原二维数组的列数 sparesArray[0][1] = colNum; //第一行第三列为原二维数组的有效元素总个数 sparesArray[0][2] = sum; //二维数组转稀疏数组 //记录稀疏数组行数 int sparesRowNum = 0; for (int i = 0; i < rowNum; i++) { for (int j = 0; j < colNum; j++) { if (chessArray[i][j] != 0) { sparesRowNum++; sparesArray[sparesRowNum][0] = i; sparesArray[sparesRowNum][1] = j; sparesArray[sparesRowNum][2] = chessArray[i][j]; } } } return sparesArray; } /** * 把稀疏数组还原成正常的二维数据 * @param sparseArray * @return */ public static int[][] toChessArray(int[][] sparseArray) { //还原行列总数 int[] initData = sparseArray[0]; int[][] chessArray = new int[initData[0]][initData[1]]; //填充原始数据 for (int i = 1; i < sparseArray.length; i++) { int[] rowData = sparseArray[i]; chessArray[i][rowData[1]] = rowData[2]; } return chessArray; } /** * 打印数据内容 */ public static void print(int[][] chessArray) { for (int[] row : chessArray) { for (int val : row) { System.out.printf("%d ", val); } System.out.println(); } } } 复制代码代码Github链接在这里
来源https://juejin.cn/post/7018361242624458789