稀疏数组

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组的处理方法是:

记录数组 一共有几行几列，有多少个不同的值（第一次遍历）把具有不同值的元素的行列及值记录在一个小规模的数组中，从而 缩小程序的规模（第二次遍历）

具体应用

使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)把稀疏数组存盘，并且可以重新恢复原来的二维数组数

整体思路分析

1.对输入的二维数组arr进行遍历，并用变量count记录arr中的有效数据个数

2.创建稀疏数组sparseArr = new int[count+1][3];

3.对sparseArr[0]初始化 sparseArr[0][0] = arr.length、sparseArr[0][1] = arr[0].length、sparseArr[0][2] = count

4.再次对arr遍历将有效数据的行、列、值记录到sparseArr中

代码实现：

public class SparseArrDemo { public static void main(String[] args) { int[][] arr = new int[5][6]; arr[1][2] = 1; arr[2][1] = 4; arr[2][3] = 3; arr[4][3] = 8; System.out.println("******************二维数组*****************"); for (int i = 0; i < arr.length; i++){ System.out.println(Arrays.toString(arr[i])); } int[][] sparseArr = toSparseArr(arr); System.out.println("******************稀疏数组*****************"); for (int i = 0; i < sparseArr.length; i++){ System.out.println(Arrays.toString(sparseArr[i])); } } //二维数组转稀疏数组 public static int[][] toSparseArr(int[][] arr){ int count = 0; //1.第一次遍历得到arr中有效数据的个数 for (int[] a:arr) { for (int i:a) { if(i != 0) count++; } } //2.创建稀疏数组,sparseArr = new int[count + 1][3] int[][] sparseArr = new int[count + 1][3]; //3.初始化稀疏数组 sparseArr[0][0] = arr.length; sparseArr[0][1] = arr[0].length; sparseArr[0][2] = count; int index = 1; //4.再次遍历arr，将有效数据的行、列、值写入稀疏数组中 for (int i = 0; i < arr.length; i++){ for (int j = 0; j < arr[0].length; j++){ if(arr[i][j] != 0){ sparseArr[index][0] = i; sparseArr[index][1] = j; sparseArr[index][2] = arr[i][j]; index++; } } } return sparseArr; } }

稀疏数组转二维数组

思路分析

1.创建二维数组arr[row][col] 其中row = sparseArr[0][0]、col = sparseArr[0][1]

2.对稀疏数组进行遍历，将有效数据填入二维数组arr

代码实现

public static int[][] to2DArr(int[][] sparseArr){ int row = sparseArr[0][0]; int col = sparseArr[0][1]; //1.创建二维数组arr[row][col] 其中row = `sparseArr`[0][0]、col = `sparseArr`[0][1] int[][] arr = new int[row][col]; //2.对稀疏数组进行遍历，将有效数据填入二维数组arr for (int i = 1; i < arr.length; i++){ arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2]; } return arr; }