稀疏数组

发布于 2022年 01月 12日 22:43

在遇到棋盘或者地图等问题时,常常需要构造一个二维数组。以棋盘为例,需要大量的0(或者其他相同的默认数值)来组成棋盘的基本结构,而数组中非0值的位置却很少。为了节省空间,可以用稀疏数组来存储相应信息。

稀疏数组是一个3列的二维数组,稀疏数组的第一行总是存储原来二维数组的行列和有效值的信息。分别是:

  1. 第一行第一列存原来二维数组的总行数
  2. 第一行第二列存原来二维数组的总列数
  3. 第一行第三列存原来二维数组的非0(有效)值的总个数

从稀疏数组的第二行往下,存放原来二维数组的有效信息,每一个有效值的信息在稀疏数组中的存放形式如下:

  1. 第1列存放某一个有效值出现的行
  2. 第2列存放那一个有效值出现的列
  3. 第3列存放那个有效的值

原来一个9*9的大数组,在使用稀疏数组后,变成一个5*3的小数组,节约了空间。图上能反应出稀疏数组与原来二维数组的对应关系。

  • 二维数组-->稀疏数组

通过遍历原来的二维数组可以找到每一个有效值的信息,然后赋值给稀疏数组。

java代码实现:

 1  public static int[][] twoToSparse(int[][] arr) {
 2         //将二维数组变成稀疏数组
 3         int sum = 0; //记录原数组有几个非0的值,用于确定稀疏数组的行数
 4         int columnNum = 0; //记录原数组的列数
 5         for (int[] ints : arr) {
 6             columnNum = ints.length; //获取列数
 7             for (int anInt : ints) {
 8                 if (anInt != 0) {
 9                     sum++;
10                 }
11             }
12         }
13         int[][] sparseArr = new int[sum + 1][3];
14         sparseArr[0][0] = arr.length;
15         sparseArr[0][1] = columnNum;
16         sparseArr[0][2] = sum;
17         int count = 0;//纪录出现的值是第几个
18         for (int i = 0; i < arr.length; i++) {  //遍历原来的二维数组,找到非0处的值,将信息赋值给稀疏数组
19             for (int j = 0; j < columnNum; j++) {
20                 if (arr[i][j] != 0) {
21                     count++; //第几个出现就放在第几行(第0行存放原数组的 总行数,总列数,总非0的值的数量)
22                     sparseArr[count][0] = i; //第一列存放行数
23                     sparseArr[count][1] = j; //第二列存放列数
24                     sparseArr[count][2] = arr[i][j]; //第三列存放具体的值
25                 }
26             }
27         }
28         return sparseArr;
29     }
  • 稀疏数组-->二维数组

通过遍历稀疏数组的信息,很快就能获得二维数组的信息,然后将原来需要的二维数组恢复。

java代码实现:

 1     public static int[][] sparseToTwo(int[][] sparseArr) {
 2         //将稀疏数组恢复成二维数组
 3         int[][] arr = new int[sparseArr[0][0]][sparseArr[0][1]]; //利用稀疏数组中第一行的总行列数信息,创建一个二维数组
 4         if (sparseArr[0][2] == 0) {
 5             return arr; //没有有效值,直接返回只有默认值的数组,这里默认值是0,不需要进行另外的赋值操作
 6         } else {
 7             for (int i = 1; i < sparseArr.length; i++) {
 8                 arr[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];  //遍历稀疏数组,读取行,列,值信息,赋给二维数组
 9 
10             }
11             return arr;
12         }
13     }

 

 

 

推荐文章