稀疏数组
之前有听到过这个数据结构，今天才彻底研究了一下
在二维数组种，如果存在大量的空位（默认为0或者其他）。会比较浪费内存，可以通过一种数据结构（稀疏数组）来表示二维数组，但是不会浪费这么多的内存。
示例
一个二维数组
[[ 0][ 0][ 0][22][ 0][ 0][15]]
[[ 0][11][ 0][ 0][ 0][17][ 0]]
[[ 0][ 0][ 0][-6][ 0][ 0][ 0]]
[[ 0][ 0][ 0][ 0][ 0][39][ 0]]
[[91][ 0][ 0][ 0][ 0][ 0][ 0]]
[[ 0][ 0][28][ 0][ 0][ 0][ 0]]
可以看到，大部分的位置都是空的（默认0）。真正的有效数据只有 8 个。一个int 4 字节一共占用了：168 字节
压缩为一个稀疏数组
[[ 6][ 7][ 8]]
* 6 表示原始数组有6行
* 7 表示原始数组有7列
* 8 表示一共有8个有效数据（非0）
[[ 0][ 3][22]]
* 0 表示第0行
* 3 表示第3列
* 22 表示第0行第3列的值是22
[[ 0][ 6][15]]
* 0 表示第0行
* 6 表示第6列
* 15 表示第0行第6列的值是22
[[ 1][ 1][11]]
[[ 1][ 5][17]]
[[ 2][ 3][-6]]
[[ 3][ 5][39]]
[[ 4][ 0][91]]
[[ 5][ 2][28]]
稀疏数组也是一个二维数组，但是只有3列。第一行记录原始数组的元信息：列数 ，行数，有效数据数
从第二行及其以后，每一行表示一个有效数据在原始数组中的行号，列号，值。
内存占用：108 字节。必原始数组少占用了 60 字节的空间
Pyhon实现
def compressed_array(arr):
# 有效的数据量
count = 0
for i in arr:
for x in i:
if x != 0:
count += 1
# 列数
col = len(arr)
# 行数
row = len(arr[0])
# 稀疏数组
ret = []
# 初始化元信息
meta_info = [col, row, count]
ret.append(meta_info)
# 遍历有效数据
for i, v in enumerate(arr):
for x, z in enumerate(v):
if z != 0:
data_info = [i, x, z]
ret.append(data_info)
return ret
def decompression_array(arr):
ret = []
# 行数
col = arr[0][0]
# 列数
row = arr[0][1]
for i in range(col):
# 初始化子数组
sub_arr = [0 for i in range(row)]
ret.append(sub_arr)
for i, sub_arr in enumerate(arr):
# 忽略第一行元数据
if i != 0:
ret[sub_arr[0]][sub_arr[1]] = sub_arr[2]
return ret
# 转换原始数组为稀疏数组
result = compressed_array([[0, 0, 0, 22, 0, 0, 15],
[0, 11, 0, 0, 0, 17, 0],
[0, 0, 0, -6, 0, 0, 0],
[0, 0, 0, 0, 0, 39, 0],
[91, 0, 0, 0, 0, 0, 0],
[0, 0, 28, 0, 0, 0, 0]])
print(result)
# 转换稀疏数组为原始数组
result = decompression_array(result)
print(result)
大多数这种问题，都是一个空间和时间的抉择。