01. 稀疏数组
稀疏数组：优化存储空间的巧妙利器
稀疏数组是一种用于高效存储大规模数据集的数据结构。通过巧妙地处理大部分元素为默认值的情况，稀疏数组在优化存储空间方面发挥了重要作用。
1. 稀疏数组的原理
稀疏数组通过巧妙地记录非默认值的元素及其位置，以达到降低存储开销的目的。其基本原理可以概括为以下几个步骤：
1.1 初始化
开始时，稀疏数组需要知道数据的大小和默认值。通常，这可以通过记录数组的行数、列数以及默认值来实现。
# 原始数组
| 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 插入非默认值
在稀疏数组中，只有非默认值的元素才需要存储。插入时，记录元素的实际值和位置。
| 默认值 | 行 | 列 |
|--------|----|----|
| 0 | 3 | 3 |
| 5 | 0 | 1 |
| 8 | 1 | 2 |1.3 压缩存储
为了进一步减小存储空间，删除默认值的记录，最终得到压缩后的稀疏数组。
| 值 | 行 | 列 |
|----|----|----|
| 5 | 0 | 1 |
| 8 | 1 | 2 |
| 0 | 3 | 3 |2. 二维数组转稀疏数组的思路
Pasted image 20231213215025
- 遍历原始的二维数组，得到有效数据的个数sum
- 根据sum创建稀疏数组sparseArr int[sum + 1][3]
- 将二维数组的有效数据存入到稀疏数组
3.稀疏数组转二维数组的思路
- 先读取稀疏数组的第一行，根据第一行数据创建原始二维数组，chessArr2 = int[11][11]
- 读取稀疏数组后几行的数据，并赋值给原始二维数组
4.Python代码实现二者转换
# 创建原始二维数组
# 0表示没有棋子，1表示黑子，2表示白子
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()
# 将二维数组转换为稀疏数组
# 1. 先遍历二维数组，得到非0的数据个数
sum_val = sum(1 for row in chess_arr1 for val in row if val != 0)
print(sum_val)
# 2. 创建对应的稀疏数组
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
# 遍历二维数组，将非0的值存放到sparse_arr中
count = 0 # 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")
# 将稀疏数组恢复成二维数组
# 1. 先读取稀疏数组的第一行，根据第一行数据创建原始二维数组，chess_arr2 = int[11][11]
# 2. 读取稀疏数组后几行的数据，并赋值给原始二维数组
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代码实现二者转换
package org.example;
public class SparseArray {
public static void main(String[] args) {
// 创建原始二维数组
// 0表示没有棋子，1表示黑子，2表示白子
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();
}
// 将二维数组转换为稀疏数组
// 1.先遍历二维数组,得到非0的数据个数
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);
// 2.创建对应的稀疏数组
int sparseArr[][] = new int[sum + 1][3];
// 给稀疏数组赋值
sparseArr[0][0] = chessArr1.length;
sparseArr[0][1] = chessArr1[0].length;
sparseArr[0][2] = sum;
// 遍历二维数组，将非0的值存放到sparseArr中
int count = 0;//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]);
}
// 将稀疏数组恢复成二维数组
// 1. 先读取稀疏数组的第一行，根据第一行数据创建原始二维数组，chessArr2 = int[11][11]
// 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();
}
}
}