时间戳

首页 > 技术文章 > 数据结构与算法之稀疏数组

数据结构与算法之稀疏数组

qsbnj 2020-08-26 21:15 原文

1.简单理解稀疏数组

可以把稀疏数组理解为只保存有效数据的一种数组，其针对的自然是有大量无用数据的数组。直接上图

原数组

 

稀疏数组

 

稀疏数组第一行类似于表格的表头，依次代表原数组的行数、列数、非零数个数（用零代表无用数据）。第一行之下的每一行都代表有一个非零数，第一列的数字代表非零数的行下标（数组下标从0开始），第二列数字代表非零数的列下标，第三列数就是非零数的实际值。

 

 

 

2.用Java代码实现普通二维数组到稀疏数组的转换及其逆过程

 1 public class SparseArray {
 2     public static void main(String[] args) throws IOException, ClassNotFoundException {
 3         //创建一个二维数组
 4         int arr1[][] = new int[11][11];
 5         arr1[1][2] = 1;
 6         arr1[2][3] = 2;
 7         arr1[2][4] = 1;
 8 
 9         //输出打印
10         System.out.println("新的二维数组：");
11         for (int[] rows : arr1) {
12             for (int i : rows) {
13                 System.out.print(i+"\t");
14             }
15             System.out.println();
16         }
17         System.out.println();
18 
19         //获取二维数组的行数、列数
20         int rowNum = arr1.length;
21         int colNum = arr1[0].length;
22         //获取非零数个数
23         int valNum = 0;
24         for (int[] rows : arr1) {
25             for (int i : rows) {
26                 if (i != 0){
27                     valNum++;
28                 }
29             }
30         }
31 
32         //依照获取的数据创建一个稀疏数组
33         int sparseArr[][] = new int[valNum+1][3];
34 
35         //设置第一行数据
36         sparseArr[0][0] = rowNum;
37         sparseArr[0][1] = colNum;
38         sparseArr[0][2] = valNum;
39 
40         //计数器
41         int count = 0;
42         for (int i = 0; i < arr1.length; i++) {
43             for (int j = 0; j < arr1[i].length; j++) {
44                 if (arr1[i][j] != 0){
45                     count++;
46                     //第n个非零数在稀疏数组中的行下标为n+1
47                     sparseArr[count][0] = i;
48                     sparseArr[count][1] = j;
49                     sparseArr[count][2] = arr1[i][j];
50                 }
51             }
52         }
53 
54         //打印稀疏数组
55         for (int[] rows : sparseArr) {
56             for (int i : rows) {
57                 System.out.print(i+"\t");
58             }
59             System.out.println();
60         }
61         System.out.println();
62 
63         //用对象输出流写入文件中
64         ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("G:\\Files\\test\\sparseArr.txt"));
65         oos.writeObject(sparseArr);
66         oos.close();
67 
68         //用对象输入流读入文件中的对象
69         ObjectInputStream ois = new ObjectInputStream(new FileInputStream("G:\\Files\\test\\sparseArr.txt"));
70         int[][] sparseArr2 = (int[][]) ois.readObject();
71         ois.close();
72 
73         //打印验证数据还原
74         System.out.println("还原的稀疏数组：");
75         for (int[] rows : sparseArr2) {
76             for (int i : rows) {
77                 System.out.print(i+"\t");
78             }
79             System.out.println();
80         }
81         System.out.println();
82 
83 
84         //将稀疏数组还原为原来的二维数组
85         int arr2[][] = new int[sparseArr2[0][0]][sparseArr2[0][1]];
86         for (int i = 1; i < sparseArr2.length; i++) {
87             arr2[sparseArr2[i][0]][sparseArr2[i][1]] = sparseArr2[i][2];
88         }
89 
90         //再次打印验证
91         for (int[] rows : arr2) {
92             for (int i : rows) {
93                 System.out.print(i+"\t");
94             }
95             System.out.println();
96         }
97 
98     }
99 }

 

推荐阅读