稀疏数组

介绍：
稀疏数组是一种对普通二维数组进行简洁描述表达的数组，即将数据量庞大的普通二维数组进行压缩记录的一种手段，并不是所有二维数组都可以转换为稀疏数组，这里说的普通数组是指值无效数据量远大于有效数据量的数组。

示例
普通二维数组，如图

0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0

其转换后的稀疏数组形式如下：

11  11  2
1   2   1
2   4   2

通过转换后，将大量无效的数据进行过滤，只针对有效数据以及数组大小进行描述，从而压缩了数组的大小。

稀疏数组转换规则
1、遍历原始二维数组，得到有效数据个数sum，示例中sum为2
2、根据sum即可创建稀疏二维数组，sparseArr[sum+1][3]。“3”是固定数值，代表3列，从第二行开始，列从左往右分别代表 行，列，有效数据值，每行代表一个数据，进行原始数据的定位。稀疏数组第一行比较特殊，列从左往右分别代表原始数组的 行数，列数，有效数据个数，方便还原时知道原始数组大小。
3、将原始二维数组的有效数据存入稀疏数组。

注意：行与列是从0开始数，方便还原时，进行位置的查找。

原始数组还原规则
1、根据稀疏数组第一行初始化数组。
2、从第二行开始将有效数值还原进二维数组。

优势
原数组中存在大量的无效数据，占据了大量的存储空间，真正有用的数据却少之又少，压缩存储可以节省存储空间以避免资源的不必要的浪费，在数据序列化到磁盘时，压缩存储可以提高IO效率。

使用场景
棋局保存或还原。
主要是在二维空间上的位置记录。

有点不成熟的小想法
可以将稀疏数组扩展成4列，分别为 长，宽，高，有效数值。即可记录三维空间的位置。或者更大胆点，可以扩展多列，记录多维的位置。

稀疏数组

原文：https://www.cnblogs.com/cowshed/p/12355274.html