一、稀疏数组的概念
当一个数组中大部分元素是0，或为同一个值的时候，可以使用稀疏数组来保存数组。它是一个十分有效的存储结构，便于节省存储空间。
稀疏数组的处理方法是：
1、记录数组一共有几行几列，有多少不同的值；
2、把具有不同值的元素的行、列及值记录在一个小规模二维数组中（稀疏数组），从而缩小存储数据的规模。
二、稀疏数组的结构
稀疏数组实际上是一个典型的二维数组，它描述的是一个标准二维数组的有效数据。
稀疏数组的行数 = 有效元素个数 + 1；
稀疏数组的列数 = 数组维度 + 1。
（二维数组转为稀疏数组，列数为3）
说明：
稀疏数组有固定的三列，分别代表原始二维数组的行、列和值。
稀疏数组的第一行存储原始数组的行数、列数和有效数据个数。
从第二行（也就是行标[1]）开始，才是真正的原始二维数组的有效数据。
示例，给出一个标准二维数组：
这个标准二维数组对应的稀疏数组的结构如下图所示：
上例中，原始二维数组为6行7列，有效元素8个（非0的数据）。转为稀疏数组后，变为9行3列。存储数据规模从42变为27，节省了部分存储空间。
注意：
稀疏数组可以描述二维数组，但同时，我认为它也可以描述更高维的数组，比如三维空间数组，那么相应稀疏数组结构也会有所变化。
所以稀疏数组并不是只能描述一个二维数组，凡是可以只保存原始数组有效数据的都可以是稀疏数组，只不过二维数组对应的稀疏数组更有代表性。
例，如果是一个三维数组，那就需要4列来保存数据，因为有3列要保存元素的坐标。
三、稀疏数组的使用条件
稀疏数组只适合有效数据少，但是数组较大的情况。
假设一个二维数组是m行n列，且有t个有效数据，那么稀疏数组的行数就是t+1，列数是3，所以只有在3(t + 1) < mn，即t < (mn) / 3 - 1时，使用稀疏数组才能有效的对数据进行压缩。
对于上例6*7的二维数组，若超过11个有效元素，使用稀疏数组反而会增加开销。
扩展：
推广到多维数组，假设n维数组可以存储s个元素，数组中有t个有效元素。
那么稀疏数组的行数就是t+1，列数是n+1。
只有在(t +1)(n +1) < s，即t < s / (n + 1) - 1时适用稀疏数组才能起到节省空间的作用。
四、稀疏数组的代码实现
以下列出Java中二维稀疏数组的实现
/**
* @author Administrator
* @date 2020/12/21
* <p>
* 稀疏数组（也是一种二维数组）
*/
class MySparseArray {
public static void main(String[] args) {
// 任意创建一个原始二维数组
int[][] array = new int[5][6];
array[0][1] = 7;
array[1][3] = 3;
array[3][4] = 10;
System.out.println("原始二维数组:");
printArray(array);
System.out.println(" ");
// 将二维数组转为稀疏数组
int[][] sparseArr = toSparseArray(array);
System.out.println("稀疏数组:");
printSparseArray(sparseArr);
// 将稀疏数组还原为二维数组
int[][] arr = toArray(sparseArr);
System.out.println("还原二维数组:");
printArray(arr);
}
/**
* 将二维数组转为稀疏数组
*/
private static int[][] toSparseArray(int[][] array) {
// 1、遍历二维数组，得到非0数据的个数
int nonZeroSum = 0;
for (int[] arr : array) {
for (int data : arr) {
if (data != 0) {
nonZeroSum++;
}
}
}
/*
2、创建对应的稀疏数组，并赋值。
据稀疏数组特性，行数为sum+1,列数固定为3
*/
int[][] sparseArr = new int[nonZeroSum + 1][3];
// 存储原二维数组的行数
sparseArr[0][0] = array.length;
// 存储原二维数组的列数
sparseArr[0][1] = array[0].length;
// 存储原二维数组的有效数据个数
sparseArr[0][2] = nonZeroSum;
// nonZeroCount用于记录是第几个非0数据
int nonZeroCount = 0;
// 3、遍历二维数组，将非0数据存放到稀疏数组中
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
if (array[i][j] != 0) {
// 定义的nonZeroCount从0开始，故必须先自增再赋值
nonZeroCount++;
// 从第二行起，给每行的第1、2、3列数据赋值
sparseArr[nonZeroCount][0] = i;
sparseArr[nonZeroCount][1] = j;
sparseArr[nonZeroCount][2] = array[i][j];
}
}
}
return sparseArr;
}
/**
* 将稀疏数组还原为二维数组
*/
private static int[][] toArray(int[][] sparseArr) {
// 1、读取稀疏数组的第一行数据，并据此创建对应的二维数组
int[][] arr = new int[sparseArr[0][0]][sparseArr[0][1]];
// 2、读取稀疏数组的剩余数据（从第二行起，故下标从1开始），并赋值给二维数组
for (int i = 1; i < sparseArr.length; i++) {
arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
return arr;
}
/**
* 输出稀疏数组
*/
private static void printSparseArray(int[][] sparseArr) {
for (int[] arr : sparseArr) {
System.out.printf("%d\t%d\t%d\t\n", arr[0], arr[1], arr[2]);
}
System.out.println();
}
/**
* 输出二维数组
*/
private static void printArray(int[][] array) {
for (int[] arr : array) {
for (int data : arr) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
}
测试结果：
五、稀疏数组的扩展
1、其他的相似类
Java中的SparseArray、LongSparseArray是泛型类。
SparseIntArray、SparseBooleanArray、SparseLongArray是非泛型类。
SparseArray还有其它的一些类似的数据结构，它们总结起来就是用于存放基本数据类型的键值对：
SparseIntArray — int:int
SparseBooleanArray— int:boolean
SparseLongArray— int:long
2、SparseArray与HashMap
（1）SparseArray与HashMap对比
优势：
1、避免了基本数据类型的装箱操作
2、不需要额外的结构体，单个元素的存储成本更低
3、数据量小的情况下，随机访问的效率更高
缺点
1、插入操作需要复制数组，增删效率降低
2、数据量巨大时，复制数组成本巨大，gc()成本也巨大
3、数据量巨大时，查询效率也会明显下降
（2）满足以下几点，SparseArray可替换HashMap
1、key为int类型
2、不需要频繁的增删操作
3、数据量不大，最好在千级以内
扩展：
1、如果key的类型已经确定为int类型，那么使用SparseArray，因为它避免了自动装箱的过程。
2、如果key为long类型，它还提供了一个LongSparseArray来确保key为long类型时的使用
3、如果key类型为其它的类型，则使用ArrayMap来替换HashMap