Conversion between sparse arrays and two-dimensional arrays using Java

Last updated on December 27, 2022 am

稀疏数组(sparse array): 非线性结构。当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。第一行保存行数、列数、数据总数。

二维数组转稀疏数组思路:
  1. 遍历原始数组,得到数据总数(sum)
  2. 创建新稀疏数组’int [sum+1] [3]’
  3. 再次遍历,将有效数据存入稀疏数组中
稀疏数组转二维数组思路:
  1. 根据稀疏数组第一行的数据,创建原始二维数组

  2. 根据稀疏数组后面几行的数据,将数据赋予原始二维数组。

例:在一个11*11的棋盘上有两个棋子,记录这两个棋子的信息。
代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//  原始二维数组,0代表无棋子,1代表黑棋,2代表白棋
int[][] chessArrayOri = new int[11][11];
chessArrayOri[1][2] = 1;
chessArrayOri[2][4] = 2;
// 打印原始二维数组
for (int[] row : chessArrayOri) {
for (int item : row) {
System.out.print(item + " ");
}
System.out.println();
}

// 二维数组转稀疏数组
int sum = 0;
for (int i = 0; i < chessArrayOri.length; i++) {
for (int j = 0; j < chessArrayOri.length; j++){
if (chessArrayOri[i][j] != 0){
sum++;
}
}
} //统计数据总数
int[][] sparseArray = new int[sum+1][3];
sparseArray[0][0] = chessArrayOri.length;
sparseArray[0][1] = chessArrayOri[0].length;
sparseArray[0][2] = sum; //构建稀疏数组第一行信息

int count = 0;
for (int i = 0; i < chessArrayOri.length; i++) {
for (int j = 0; j < chessArrayOri.length; j++){
if (chessArrayOri[i][j] != 0){
count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = chessArrayOri[i][j];
}
}
} //将数据存入稀疏数组

System.out.println("===================================");
for (int[] row : sparseArray) {
for (int item : row) {
System.out.print(item + " ");
}
System.out.println();
} //打印生成的稀疏数组

// 稀疏数组转二维数组
int[][] chessArr = new int[sparseArray[0][0]][sparseArray[0][1]];
for (int i = 1; i < sparseArray.length; i++){
chessArr[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
} //生成二维数组

System.out.println("==========================================");
for (int[] row : chessArr) {
for (int item : row) {
System.out.print(item + " ");
}
System.out.println();
} //打印还原的二维数组

Conversion between sparse arrays and two-dimensional arrays using Java
http://hihiko.zxy/2022/12/27/Conversion-between-sparse-arrays-and-two-dimensional-arrays-using-Java/
Author
Posted on
December 27, 2022
Licensed under