Conversion between sparse arrays and two-dimensional arrays using Java
Last updated on December 27, 2022 am
稀疏数组(sparse array): 非线性结构。当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。第一行保存行数、列数、数据总数。
二维数组转稀疏数组思路:
- 遍历原始数组,得到数据总数(sum)
- 创建新稀疏数组’int [sum+1] [3]’
- 再次遍历,将有效数据存入稀疏数组中
稀疏数组转二维数组思路:
根据稀疏数组第一行的数据,创建原始二维数组
根据稀疏数组后面几行的数据,将数据赋予原始二维数组。
例:在一个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
| 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/