一、什么是sparsearray
sparsearray(稀疏数组)是一种压缩存储数据的方式,它通常用于解决数据中存在大量空值(一般为默认值)的情况。稀疏数组是将二位数组转换为一维数组来节省存储空间的一种方法。
如果数组中大部分元素值为0或者同一个值时,我们就可以使用稀疏数组来代替原始的数组,从而节省内存空间。稀疏数组的转换方法为记录存储有值的元素的行列值以及对应的值,最后将这些元素存储到新的数组中。
// 稀疏数组的创建 int[][] chessArr = new int[11][11]; // 填充原数组 chessArr[1][2] = 1; chessArr[2][3] = 2; // 输出原数组 for (int[] row : chessArr) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } // 将原数组压缩为稀疏数组 int sum = 0; for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (chessArr[i][j] != 0) { sum++; } } } int[][] sparseArr = new int[sum + 1][3]; sparseArr[0][0] = 11; sparseArr[0][1] = 11; sparseArr[0][2] = sum; int count = 0; for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (chessArr[i][j] != 0) { count++; sparseArr[count][0] = i; sparseArr[count][1] = j; sparseArr[count][2] = chessArr[i][j]; } } } // 输出稀疏数组 for (int[] row : sparseArr) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); }
二、sparsearray的应用场景
sparsearray适用于当数据中某些元素的值非常规律且大量为同一个值时;或者当元素值很大且大部分为0时,可以使用稀疏数组来保存这些数据。下面是一些实际应用场景:
1.棋盘
一张棋盘大部分情况下都是没有棋子的,而只有少数的点放置了棋子。因此我们可以使用稀疏数组来节省存储空间。
int[][] chessBoard = new int[11][11]; chessBoard[1][2] = 1; chessBoard[2][3] = 2; int[][] sparseArr = toSparseArr(chessBoard);
2、象棋
象棋是一种对称性较高的棋类,当仅有一方存在棋子时,我们可以使用稀疏数组来保存信息。
int[][] checkerboard = new int[10][9]; checkerboard[0][0] = 1; int[][] sparseArr = toSparseArr(checkerboard);
3、数组操作记录
当我们需要对一个数组进行多次操作并记录每次操作的结果时,可以使用稀疏数组来记录这些操作。
int[][] arr = new int[3][3]; arr[0][2] = 1; arr[1][1] = 2; int[][] sparseArr = toSparseArr(arr); // 对稀疏数组中的元素进行操作 sparseArr[1][2] = 3; int[][] arr2 = toArr(sparseArr); for (int[] row: arr2) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); }
三、sparsearray的应用示例
下面是一个动态展示将稀疏数组转换回原始数组的过程:
import java.util.Arrays; public class SparseArray { public static void main(String[] args) { // 创建原始二维数组 11 * 11 // 0: 表示没有棋子, 1 表示黑子 2 表示蓝子 int[][] chessArr1 = new int[11][11]; chessArr1[1][2] = 1; chessArr1[2][3] = 2; // 输出原始二维数组 System.out.println("原始二维数组:"); for (int[] row : chessArr1) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } // 转换成稀疏数组 int[][] sparseArr = toSparseArr(chessArr1); // 输出稀疏数组 System.out.println("稀疏数组:"); for (int[] row : sparseArr) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } // 转换回原始二维数组 int[][] chessArr2 = toArr(sparseArr); // 输出转换后的二维数组 System.out.println("转换后的二维数组:"); for (int[] row : chessArr2) { for (int data : row) { System.out.printf("%d\t", data); } System.out.println(); } } /** * 将二维数组转换为稀疏数组 * @param chessArr 二维数组 * @return 稀疏数组 */ public static int[][] toSparseArr(int[][] chessArr) { // 原始数组共有多少个非0值 int sum = 0; for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (chessArr[i][j] != 0) { sum++; } } } // 创建稀疏数组 int[][] sparseArr = new int[sum + 1][3]; // 为稀疏数组赋值 sparseArr[0][0] = 11; sparseArr[0][1] = 11; sparseArr[0][2] = sum; // 遍历原始数组,将非0值存入稀疏数组 int count = 0; for (int i = 0; i < 11; i++) { for (int j = 0; j < 11; j++) { if (chessArr[i][j] != 0) { count++; sparseArr[count][0] = i; sparseArr[count][1] = j; sparseArr[count][2] = chessArr[i][j]; } } } return sparseArr; } /** * 将稀疏数组恢复成原始二维数组 * @param sparseArr 稀疏数组 * @return 原始二维数组 */ public static int[][] toArr(int[][] sparseArr) { // 创建原始二维数组 int[][] arr = new int[sparseArr[0][0]][sparseArr[0][1]]; // 遍历稀疏数组,将值赋给原始二维数组 for (int i = 1; i < sparseArr.length; i++) { arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2]; } return arr; } }