稀疏数组

[Zakariyya]

当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用系数数组来保存该数组

处理方式：

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

eg，五子棋（一个 6 * 7 = 42 的棋盘）:

(原始二维数组)

    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   25  0   0   0   0

因为该二维数组的很多值默认是0，因此记录了很多没有意义的数据，我们需要压缩将其转换成 稀疏数组

换成 稀疏数组

	行	列	值
[0]	6	7	8
[1]	0	3	22
[2]	0	6	15
[3]	1	1	11
[4]	1	5	17
[5]	2	3	-6
[6]	3	5	39
[7]	4	0	91
[8]	5	2	28

• [0]行6，代表数组一共有6行
• [0]列7，代表数组一共有7列
• [0]值8，代表全数组有8个值

下面每一行都代表了非零值的行列

• [1]第0行，第 下标为3 的列，值为22
• [2]第1行，第 下标为6 的列，值为15
• [3]第2行，第 下标为1 的列，值为11

稀疏后数组从 6 7 = 42 变成 9 3 = 27 的数组

应用实例

五子棋，棋盘

一个原始二维数组: 11 * 11

(原始二维数组)

    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   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   0

换成稀疏数组：3 * 3

    row         col           val
0   11      11      2
1   1       2       1
2   2       3       2

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

1. 遍历 原始的二维数组，得到有效数据的个数 sum 用来决定稀疏数组的大小
2. 根据sum 就可以创建 稀疏数组sparseArr int[sum+1][3]
3. 将二维数组的有效数据存入 稀疏数组

   稀疏数组的第一行，存的就是原始数组的行和列

稀疏数组 转 原始二维数组 的思路

1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2 = int[11][11]
2. 再读取稀疏数组后几行的数据，并赋给 原始的二维数组即可。