一、什么是稀疏数组
稀疏数组：是一个数组，他的作用是将二维数据保存的值进行优化，减小储存数据的大小。
格式：稀疏素组是一个(n+1)*3的二维数组，其中n表示二维数组中有多少个不同的值。稀疏数组，第一行保存，二维数据的行、列、不同的值得个数；剩余行保存不同值的坐标、值；
举例：
如下数组为一个11*11的二维数组，有3个位置不是0，所以n为3。此例中保存二维数组需要保存11*11个数字，保存稀疏数组需要4*3个。
二维数组：
1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
稀疏数组：
11 11 3 0 0 1 0 3 1 1 1 1
适用场景
当一个数组中大部分元素为0，或者为同一个值得数组时，可以使用稀疏数组来保存该数组；在11*11的场景中，如果不一样的数据超过39个，不适合使用稀疏数组(不考虑数据地址的细节)。
二、二维数据如何转换为稀疏数组
// 二维数组转稀疏数组 private static int[][] array2SparsArray(int[][] array) { //获取二维数据行和列 int rowLength = array.length; int colLength = array[0].length; //获取不一样的数据 int sum = 0; for (int i = 0; i < rowLength; i++) { for (int j = 0; j < colLength; j++) { if (array[i][j] != 0) { sum++; } } } //初始化稀疏数组 int[][] sparsArray = new int[sum + 1][3]; //第一行保存二维数组的大小和不一样值得个数 sparsArray[0][0] = rowLength; sparsArray[0][1] = colLength; sparsArray[0][2] = sum; //遍历二维数据，将不同的值的坐标和值保存到稀疏数组 //记录稀疏数组的行 int count = 0; for (int i = 0; i < rowLength; i++) { for (int j = 0; j < colLength; j++) { if (array[i][j] != 0) { count++; //保存二维数组的坐标 sparsArray[count][0] = i; sparsArray[count][1] = j; //保存二维数组的值 sparsArray[count][2] = array[i][j]; } } } return sparsArray; }
三、稀疏数组如何恢复为二维数组
// 稀疏数组转二维数组 private static int[][] sparsArray2Array(int[][] sparsArray) { //获取二维数据行和列 int rowLength = sparsArray[0][0]; int colLength = sparsArray[0][1]; //初始化二维数组 int[][] array = new int[rowLength][colLength]; int sparsArrayLength = sparsArray.length; for (int i = 1; i < sparsArrayLength; i++) { //回复二维数组中不一样的值 array[sparsArray[i][0]][sparsArray[i][1]] = sparsArray[i][2]; } return array; }
四、完整代码并测试
public class sparsearray { public static void main(String[] args) { int[][] array1 = new int[11][11]; array1[0][0] = 1; array1[1][1] = 1; array1[0][3] = 1; System.out.println("打印二维数组"); printArray(array1); int[][] sparsArray = array2SparsArray(array1); System.out.println("打印二维数组转换后的稀疏数组"); printArray(sparsArray); System.out.println("打印稀疏数组回复后的二维数据"); int[][] array2 = sparsArray2Array(sparsArray); printArray(array2); } // 二维数组转稀疏数组 private static int[][] array2SparsArray(int[][] array) { //获取二维数据行和列 int rowLength = array.length; int colLength = array[0].length; //获取不一样的数据 int sum = 0; for (int i = 0; i < rowLength; i++) { for (int j = 0; j < colLength; j++) { if (array[i][j] != 0) { sum++; } } } //初始化稀疏数组 int[][] sparsArray = new int[sum + 1][3]; //第一行保存二维数组的大小和不一样值得个数 sparsArray[0][0] = rowLength; sparsArray[0][1] = colLength; sparsArray[0][2] = sum; //遍历二维数据，将不同的值的坐标和值保存到稀疏数组 //记录稀疏数组的行 int count = 0; for (int i = 0; i < rowLength; i++) { for (int j = 0; j < colLength; j++) { if (array[i][j] != 0) { count++; //保存二维数组的坐标 sparsArray[count][0] = i; sparsArray[count][1] = j; //保存二维数组的值 sparsArray[count][2] = array[i][j]; } } } return sparsArray; } // 稀疏数组转二维数组 private static int[][] sparsArray2Array(int[][] sparsArray) { //获取二维数据行和列 int rowLength = sparsArray[0][0]; int colLength = sparsArray[0][1]; //初始化二维数组 int[][] array = new int[rowLength][colLength]; int sparsArrayLength = sparsArray.length; for (int i = 1; i < sparsArrayLength; i++) { //回复二维数组中不一样的值 array[sparsArray[i][0]][sparsArray[i][1]] = sparsArray[i][2]; } return array; } // 二维数组打印 private static void printArray(int[][] array) { int rowLength = array.length; int colLength = array[0].length; for (int i = 0; i < rowLength; i++) { for (int j = 0; j < colLength; j++) { System.out.printf("%d\t", array[i][j]); } System.out.println(); } } // 稀疏数组存盘 // 读取稀疏数组 }
打印二维数组 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 打印二维数组转换后的稀疏数组 11 11 3 0 0 1 0 3 1 1 1 1 打印稀疏数组回复后的二维数据 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
