稀疏数组：优化存储空间的巧妙利器
稀疏数组是一种用于高效存储大规模数据集的数据结构。通过巧妙地处理大部分元素为默认值的情况，稀疏数组在优化存储空间方面发挥了重要作用。
1. 稀疏数组的原理
稀疏数组通过巧妙地记录非默认值的元素及其位置，以达到降低存储开销的目的。其基本原理可以概括为以下几个步骤：
1.1 初始化
开始时，稀疏数组需要知道数据的大小和默认值。通常，这可以通过记录数组的行数、列数以及默认值来实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| # 原始数组
| 0 | 0 | 0 | 0 |
| 0 | 5 | 0 | 0 |
| 0 | 0 | 8 | 0 |
| 0 | 0 | 0 | 0 |
# 稀疏数组
| 值 | 行 | 列 |
|----|----|----|
| 5 | 1 | 1 |
| 8 | 2 | 2 |
# 初始化
| 默认值 | 行 | 列 |
|--------|----|----|
| 0 | 3 | 3 |
|
1.2 插入非默认值
在稀疏数组中，只有非默认值的元素才需要存储。插入时，记录元素的实际值和位置。
1
2
3
4
5
| | 默认值 | 行 | 列 |
|--------|----|----|
| 0 | 3 | 3 |
| 5 | 0 | 1 |
| 8 | 1 | 2 |
|
1.3 压缩存储
为了进一步减小存储空间，删除默认值的记录，最终得到压缩后的稀疏数组。
1
2
3
4
5
| | 值 | 行 | 列 |
|----|----|----|
| 5 | 0 | 1 |
| 8 | 1 | 2 |
| 0 | 3 | 3 |
|
2. 二维数组转稀疏数组的思路
- 遍历原始的二维数组，得到有效数据的个数sum
- 根据sum创建稀疏数组sparseArr int[sum + 1][3]
- 将二维数组的有效数据存入到稀疏数组
3.稀疏数组转二维数组的思路
- 先读取稀疏数组的第一行，根据第一行数据创建原始二维数组，chessArr2 = int[11][11]
- 读取稀疏数组后几行的数据，并赋值给原始二维数组
4.Python代码实现二者转换
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
|
chess_arr1 = [[0] * 11 for _ in range(11)]
chess_arr1[1][2] = 1
chess_arr1[2][3] = 2
print("原始二维数组")
for row in chess_arr1:
for data in row:
print(f"{data}\t", end="")
print()
sum_val = sum(1 for row in chess_arr1 for val in row if val != 0)
print(sum_val)
sparse_arr = [[0, 0, 0] for _ in range(sum_val + 1)]
sparse_arr[0][0] = len(chess_arr1)
sparse_arr[0][1] = len(chess_arr1[0])
sparse_arr[0][2] = sum_val
count = 0
for i in range(len(chess_arr1)):
for j in range(len(chess_arr1[i])):
if chess_arr1[i][j] != 0:
count += 1
sparse_arr[count][0] = i
sparse_arr[count][1] = j
sparse_arr[count][2] = chess_arr1[i][j]
print("\n得到的稀疏数组为")
for row in sparse_arr:
print(f"{row[0]}\t{row[1]}\t{row[2]}\t")
chess_arr2 = [[0] * sparse_arr[0][1] for _ in range(sparse_arr[0][0])]
for i in range(1, len(sparse_arr)):
chess_arr2[sparse_arr[i][0]][sparse_arr[i][1]] = sparse_arr[i][2]
print("\n恢复后的二维数组")
for row in chess_arr2:
for data in row:
print(f"{data}\t", end="")
print()
|
5.Java代码实现二者转换
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
60
61
62
63
64
65
66
67
68
69
70
71
| package org.example;
public class SparseArray {
public static void main(String[] args) {
int chessArr1[][] = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
System.out.println("原始二维数组");
for (int[] row : chessArr1) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
int sum = 0;
for (int i = 0; i < chessArr1.length; i++) {
for (int j = 0; j < chessArr1[i].length; j++) {
if (chessArr1[i][j] != 0) {
sum++;
}
}
}
System.out.println(sum);
int sparseArr[][] = new int[sum + 1][3];
sparseArr[0][0] = chessArr1.length;
sparseArr[0][1] = chessArr1[0].length;
sparseArr[0][2] = sum;
int count = 0;
for (int i = 0; i < chessArr1.length; i++) {
for (int j = 0; j < chessArr1[i].length; j++) {
if (chessArr1[i][j] != 0) {
count++;
sparseArr[count][0]=i;
sparseArr[count][1]=j;
sparseArr[count][2]=chessArr1[i][j];
}
}
}
System.out.println();
System.out.println("得到的稀疏数组为");
for (int i = 0; i < sparseArr.length; i++) {
System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
}
int chessArr2[][]=new int[sparseArr[0][0]][sparseArr[0][1]];
for (int i = 1; i < sparseArr.length; i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
}
System.out.println();
System.out.println("恢复后的二维数组");
for (int[] row : chessArr2) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
}
|
