Java实现稀疏数组
2021-01-22 19:13
标签：turn mic col 数值 public height 计算 数组 ESS 如果一个数组(包括多维数组)中的大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组，节约空间。 一般来说，稀疏数组的处理方法是： 1.记录数组一共有几行几列，有多少个不同的数值。 1、可以使用稀疏数组来保留类似前面的二维数组(棋盘，地图等)。 Java实现稀疏数组 标签：turn mic col 数值 public height 计算 数组 ESS 原文地址：https://www.cnblogs.com/cq-yangzhou/p/12888504.html1、概念
2.把具有不同值的元素的行列记录在一个小规模的数组中，从而缩小程序的规模。
如图所示，一般来说，第一行存取几行几列以及几个不同的数值。
2、应用
2、把稀疏数组存盘，并且可以重新恢复原来的二维数组数。3、Java代码实现
（1）、原始数组转换为稀疏数组
1 /***
2 * 将原始数组转换为稀疏数组
3 * @param arr
4 * @return
5 */
6 private static int[][] arr2SparseArray(int[][] arr){
7 int length_hang = arr.length,legtn_lie = arr[0].length,sum = 0;
8 //计算非零元素个数
9 for (int i = 0; i ) {
10 for (int j = 0; j ) {
11 if (0!= arr[i][j]){
12 sum++;
13 }
14 }
15 }
16 int[][]sparseArray = new int[sum+1][3];
17 //第一行分别代表原始数组的行数、列数和非零元素个数
18 sparseArray[0][0] = length_hang;
19 sparseArray[0][1] = legtn_lie;
20 sparseArray[0][2] = sum;
21 //遍历原始数组，记录非零元素的坐标和值
22 int inex = 1;
23 for (int i = 0; i ) {
24 for (int j = 0; j ) {
25 if (0!= arr[i][j]){
26 sparseArray[inex][0] = i;
27 sparseArray[inex][1] = j;
28 sparseArray[inex][2] = arr[i][j];
29 inex++;
30 }
31 }
32 }
33 return sparseArray;
34 }
（2）、稀疏数组恢复为原始数组
1 /**
2 * 稀疏数组恢复原始数组
3 * @param sparseArray
4 * @return
5 */
6 private static int[][] sparseArray2Arr(int[][]sparseArray){
7 //读取原始数组的行和列（稀疏数组第一行）
8 int length_hang = sparseArray[0][0],length_lie = sparseArray[0][1];
9 int[][] arr = new int[length_hang][length_lie];
10 //从第二行开始遍历稀疏数组，恢复非零元素
11 for (int i = 1; i ) {
12 arr[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
13 }
14 return arr;
15 }
4、测试
1 public static void main(String[] args) {
2 int[][] arr = new int[6][7];
3 arr[0][3] = 22;
4 arr[0][6] = 15;
5 arr[1][1] = 11;
6 arr[1][5] = 17;
7 arr[2][3] = -6;
8 arr[3][5] = 39;
9 arr[4][0] = 91;
10 arr[5][2] = 28;
11
12 System.out.println("=================原始数组===================");
13 for (int[] ints : arr) {
14 for (int a : ints) {
15 System.out.print(a+"\t");
16 }
17 System.out.println();
18 }
19 System.out.println("==================变换为稀疏数组============");
20 int[][]sparseArray = arr2SparseArray(arr);
21 for (int[] ints : sparseArray) {
22 for (int a : ints) {
23 System.out.print(a+"\t");
24 }
25 System.out.println();
26 }
27 System.out.println("==================恢复为原始数组============");
28 int[][] arr1 = sparseArray2Arr(sparseArray);
29 for (int[] ints : arr1) {
30 for (int a : ints) {
31 System.out.print(a+"\t");
32 }
33 System.out.println();
34 }
35 }
5、结果
1 =================原始数组===================
2 0 0 0 22 0 0 15
3 0 11 0 0 0 17 0
4 0 0 0 -6 0 0 0
5 0 0 0 0 0 39 0
6 91 0 0 0 0 0 0
7 0 0 28 0 0 0 0
8 ==================变换为稀疏数组============
9 6 7 8
10 0 3 22
11 0 6 15
12 1 1 11
13 1 5 17
14 2 3 -6
15 3 5 39
16 4 0 91
17 5 2 28
18 ==================恢复为原始数组============
19 0 0 0 22 0 0 15
20 0 11 0 0 0 17 0
21 0 0 0 -6 0 0 0
22 0 0 0 0 0 39 0
23 91 0 0 0 0 0 0
24 0 0 28 0 0 0 0
25
26 Process finished with exit code 0
下一篇：Java-int 中加下划线