简介
稀疏数组是一种数据结构，用于有效地存储和处理那些大多数元素都是零或者重复值的数组。在稀疏数组中，只有非零或非重复的元素会被存储，从而节省内存空间。
案例引入
假如想把下面这张表存入文件，我们会怎么做？
如果我们不做优化其实是浪费了很大一部分空间去存储空值，有没有办法既能实现效果又能节省空间呢？其实有的，稀疏数组就可以做到。
假如我们只存储右边的数据，相对左边做了相对大的数据压缩，会把空数据也就是无效的数据过滤，只存储有效的数据。
稀疏数组结构解释：
[0][0] - 记录原二维数组有几行
[0][1] - 记录原二维数组有几列
[0][2] - 记录原二维数组有多少个有效的数据
后面的一次记录有效数据所在行和列及有效数据的具体值
1，我们先将上图中的第一个数据结构转成程序中的二维数组
//1，将棋盘中的1，2用二维数组保存起来
int[][] chessArray = new int[11][11];
chessArray[1][2] = 1;
chessArray[2][3] = 2;
System.out.println("将棋盘转换为原始的二维数组");
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
System.out.printf("%d\t", chessArray[i][j]);
}
System.out.println();
}
//2，将棋盘chessArray转出稀疏数组
//稀疏数组一共有 row 3 col sum+1 第一行第一列未i行，第一行第二列为j列，第三个为num有效数据
//第一步先要找出上述棋盘一共有多少个有效数据，计为sum
int sum = 0;//默认0个有效数据
for (int[] row : chessArray) {
for (int data : row) {
if (data != 0) {
sum++;
}
}
}
//转换的稀疏数组
int[][] sparseArray = new int[sum + 1][3];
//将有效数据保存到稀疏数组中
sparseArray[0][0] = chessArray.length;
sparseArray[0][1] = chessArray.length;
sparseArray[0][2] = sum;
int count = 0;
for(int i = 0;i<chessArray.length;i++){
for(int j = 0 ;j<chessArray.length;j++){
if(chessArray[i][j]!=0){
count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = chessArray[i][j];
}
}
}
System.out.println("转换的稀疏数组为");
for(int []rows : sparseArray){
for(int data:rows){
System.out.printf("%d\t",data);
}
System.out.println();
}
//将稀疏数组转出原始数组
//1，读取第一行创建原始数组的大小
int [][] chessArray2 = new int[sparseArray[0][0]][sparseArray[0][1]];
System.out.println();
System.out.println("原始数组"+sparseArray[0][0]+" "+sparseArray[0][1]);
for(int i = 1;i<sparseArray.length;i++){
chessArray2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
System.out.println("转换的原始数组");
for(int []rows : chessArray2){
for(int data:rows){
System.out.printf("%d\t",data);
}
System.out.println();
}
总结
从上面的案例中，我们能感受到稀疏数组的一些特点：
存储效率：由于只存储非零或非重复的元素，稀疏数组在处理大量零值或重复值的数据时非常高效。
空间优化：相比于传统的数组，稀疏数组可以显著减少所需的存储空间。
稀疏性：稀疏数组中的元素大部分是零或重复值，这些值不需要存储。
实现方式：稀疏数组可以通过多种方式实现，例如使用哈希表、链表、位图或压缩存储等。
适用场景：稀疏数组适用于那些元素值重复或为零的情况，例如图的邻接矩阵、大规模数据集、科学计算中的矩阵等。
访问速度：虽然稀疏数组在存储上很高效，但访问速度可能会比传统数组慢，因为需要额外的查找步骤来定位非零元素。
更新和删除：在稀疏数组中更新或删除元素可能比在传统数组中更复杂，因为需要维护非零元素的索引或映射。
稀疏度：稀疏数组的效率很大程度上取决于其稀疏度，即非零或非重复元素占总元素的比例。稀疏度越高，稀疏数组的优势越明显。
总的来说，稀疏数组是一种针对特定数据特性优化的数据结构，可以在特定场景下提供存储和处理上的优势。
