是否存在比一位数组更好的,用来存储含有大量'0'的数据结构呢?
需要存储一个线性表,而且数据量比较大。现在我可以通过计算得出我想要的那个数据在这个线性表中的索引位置,然后通过索引来获得想要的数据。
用一维数组就可以存储。若数据有N个,那么空间复杂度为O(N),获得数据的时间复杂度为O(1)。
问题:但是,这个数据集里有大量的0,也就意味着,有很多地方会出现连续很多个0,那么是否可以针对这一点,对这一位数组改进一下,降低它的存储空间呢?并且,最好使得获得数据的时间复杂度不要上升太多(毕竟O(1)已经是最短的时间了,变慢一点还是可以接受的,这里的瓶颈是存储空间)。
[解决办法]
storage = dict()
# 存储
if y:
storage[x] = y
..
# 提取
y = storage.get(x, 0)
[解决办法]
用dict最好了吧
d = {id:num};
d.get(id,0);