稀疏数组

2019-10-13 本文已影响0人 spraysss

当数组中的大部分元素为0，或者同一值时，可以使用稀疏数组来存储该数组，使用稀疏矩阵可以节约存储空间
稀疏数组的处理方法是：

记录数组有几行几列，有多少个不同值
把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

举个例子,如下 $7\times6$ 的矩阵，进过稀疏处理后，第一行7，6，5代表原矩阵有7行6列 5个值，第二行的0，2，1代表在第0行第2列的值为1，以此类推，可以看到通过稀疏矩阵处理后，矩阵大小变为 $7\times3$ ,减少了存储空间
$\begin{pmatrix} {0}&{0}&{1}&{0}&{0}&{0}\\ {0}&{0}&{0}&{3}&{0}&{0}\\ {0}&{2}&{0}&{0}&{0}&{0}\\ {0}&{0}&{0}&{0}&{4}&{0}\\ {5}&{0}&{0}&{0}&{0}&{0}\\ {0}&{0}&{2}&{0}&{0}&{0}\\ {0}&{0}&{0}&{0}&{0}&{0}\\ \end{pmatrix} =>\begin{pmatrix} {7}&{6}&{5}\\ {0}&{2}&{1}\\ {1}&{3}&{3}\\ {2}&{1}&{2}\\ {3}&{4}&{4}\\ {4}&{0}&{5}\\ {5}&{2}&{2}\\ \end{pmatrix}$

稀疏数组

猜你喜欢

热点阅读