01. 稀疏数组

2024 年 7 月 18 日 星期四(已编辑)
/ ,
1
这篇文章上次修改于 2024 年 7 月 18 日 星期四,可能部分内容已经不适用,如有疑问可询问作者。

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

Pasted image 20231213215025
  1. 遍历原始的二维数组,得到有效数据的个数sum
  2. 根据sum创建稀疏数组sparseArr int[sum + 1][3]
  3. 将二维数组的有效数据存入到稀疏数组

3.稀疏数组转二维数组的思路

  1. 先读取稀疏数组的第一行,根据第一行数据创建原始二维数组,chessArr2 = int[11][11]
  2. 读取稀疏数组后几行的数据,并赋值给原始二维数组

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();  
        }  
    }  
}
  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...