Ⅰ、为什么用稀疏数组？
比如这个棋盘，如果要记录黑蓝棋子的位置首先会想到运用二维数组，我们把二维数组建好后（1是黑，2是蓝），发现很多空白位置浪费了大量的内存空间
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来存储给数组。我们这个时候可以用稀疏数组来存储“有效数据”
Ⅱ、怎么使用稀疏数组？
稀疏数组一共有三列（列固定），分别表示行号，列号和值
第一行：记录初始数组的总共行、总共列、有效值的个数（有意义的值）
其他行：逐次记录有效值的行号、列号和值
由图可知，稀疏数组总行数为有效值 + 1 （假设有效值为num）行数为num + 1， 列数固定为3。 (左图为二维数组，右图为稀疏数组)
Ⅲ、二维数组转稀疏数组
- 遍历原始的二维数组，得到有效数据的个数sum。
- 根据sum就可以创建稀疏数组sparseArray int [sum + 1] [3]
- 将二维数组的有效数据存入稀疏数组
实例：(以下定义了一个方法用来转换矩阵二维数组转换为稀疏数组) (二维数组类型不同可重载，可直接修改方法中的 int)
// 定义一个将原始二维数组转换为稀疏数组的方法 (传入参数必须是矩阵二维数组)
public static int[][] toSparseArray(int[][] array){
int sum = 0; // 用来存储有效值的个数
// 通过for each增强循环遍历确定有效值的个数
for (int[] a: array) {
for (int b: a) {
if (b != 0){
sum ++;
}
}
}
// 创建稀疏数组SparseArray (行数为有效值 + 1， 列数固定为3)
int[][] SparseArray = new int[sum + 1][3];
// 给稀疏数组ParseArray第一行赋值
SparseArray[0][0] = array.length; // 原始二维数组最外层的元素个数
SparseArray[0][1] = array[0].length; // 原始二维数组最里层的元素个数
SparseArray[0][2] = sum; // 原始二维数组的有效值 + 1
// 遍历原始二维数组将有效值赋值给稀疏数组
int row = 1; // 用来更新赋值给稀疏数组的行数
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
if (array[i][j] != 0){
SparseArray[row][0] = i; // 有效值的行
SparseArray[row][1] = j; // 有效值列
SparseArray[row][2] = array[i][j]; // 有效值的值
row++;
}
}
}
return SparseArray; // 返回转换后的稀疏数组
}
完整实例：
public class MusicDay {
public static void main(String[] args) {
// 声明创建一个原始二维数组 (8 * 8)
int[][] array = new int[8][8];
array[1][2] = 1;
array[2][3] = 2;
// for-each增强循环遍历原始二维数组 输出原始二维数组
System.out.println("原始二维数组为：");
for (int[] b : array) {
for (int c: b) {
System.out.print(c + "\t");
}
System.out.println();
}
// 调用方法并接收转换为稀疏数组的返回值
int[][] SparseArray = toSparseArray(array);
System.out.println("转换为稀疏数组为：");
// for-each增强循环遍历转换后的稀疏数组 输出稀疏数组
for (int[] b : SparseArray) {
for (int c: b) {
System.out.print(c + "\t");
}
System.out.println();
}
}
// ==============================================================
// 定义一个将原始二维数组转换为稀疏数组的方法 (传入参数必须是矩阵)
public static int[][] toSparseArray(int[][] array){
int sum = 0; // 用来存储有效值的个数
// 通过for each增强循环遍历确定有效值的个数
for (int[] a: array) {
for (int b: a) {
if (b != 0){
sum ++;
}
}
}
// 创建稀疏数组SparseArray (行为有效值 + 1， 列固定为3)
int[][] SparseArray = new int[sum + 1][3];
// 给稀疏数组ParseArray第一行赋值
SparseArray[0][0] = array.length; // 原始二维数组最外层的元素个数
SparseArray[0][1] = array[0].length; // 原始二维数组最里层的元素个数
SparseArray[0][2] = sum; // 原始二维数组的有效值 + 1
// 遍历原始二维数组将有效值赋值给稀疏数组
int row = 1; // 用来更新稀疏数组赋值的行数
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[0].length; j++) {
if (array[i][j] != 0){
SparseArray[row][0] = i; // i为有效值的行
SparseArray[row][1] = j; // j为有效值的列
SparseArray[row][2] = array[i][j]; // 有效值的值
row++;
}
}
}
return SparseArray; // 返回转换后的稀疏数组
}
}
输出结果为：
原始二维数组为： 0 0 0 0 0 0 0 0 0 0 1 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 转换为稀疏数组为： 8 8 2 1 2 1 2 3 2
Ⅳ、稀疏数组转原始数组
- 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组。
- 在读取稀疏数组后几行的数据，并赋给原始的二维数组即可。
实例：(以下定义了将稀疏数组转换为原始二维数组的方法)
// 定义toArray方法作用为将稀疏数组转换为原始二维数组
public static int[][] toArray(int[][] SparseArray){
// 通过稀疏数组的第一行前两个元素确定原始二维数组的行数列数
int[][] Array = new int[SparseArray[0][0]][SparseArray[0][1]];
// 通过循环为原始二维数组赋值
for (int i = 1; i < SparseArray.length; i++) {
Array[SparseArray[i][0]][SparseArray[i][1]] = SparseArray[i][2];
}
return Array; // 返回转换后的原始二维数组
}
完整实例：
public class MusicDay {
public static void main(String[] args) {
// 声明创建稀疏数组 第一个3代表有2个有效值，第二个3为稀疏数组固定列数。
int[][] SparseArray = new int[3][3];
// 为稀疏数组赋值
SparseArray[0][0] = 8; // 对应二维数组的行数
SparseArray[0][1] = 8; // 对应二维数组的列数
SparseArray[0][2] = 2; // 有效值的个数
SparseArray[1][0] = 2; // 第一个有效值的行数
SparseArray[1][1] = 3; // 第一个有效值的行数
SparseArray[1][2] = 1; // 第一个有效值的具体值
SparseArray[2][0] = 3;
SparseArray[2][1] = 4;
SparseArray[2][2] = 2;
// 输出创建的稀疏数组
System.out.println("稀疏数组为：");
for (int[] a: SparseArray) {
for (int b: a) {
System.out.print(b + "\t");
}
System.out.println();
}
// 调用toArray方法并接收返回转换后的原始二维数组
int [][] Array = toArray(SparseArray);
// 输出转换后的原始二维数组
System.out.println("转换后的原始二维数组为：");
for (int[] a: Array) {
for (int b: a) {
System.out.print(b + "\t");
}
System.out.println();
}
}
// =======================================================
// 定义toArray方法作用为将稀疏数组转换为原始二维数组
public static int[][] toArray(int[][] SparseArray){
// 通过稀疏数组的第一行前两个元素确定原始二维数组的行数列数
int[][] Array = new int[SparseArray[0][0]][SparseArray[0][1]];
// 通过循环为原始二维数组赋值
for (int i = 1; i < SparseArray.length; i++) {
Array[SparseArray[i][0]][SparseArray[i][1]] = SparseArray[i][2];
}
return Array; // 返回转换后的原始二维数组
}
}
输出结果为：
稀疏数组为： 8 8 2 2 3 1 3 4 2 转换后的原始二维数组为： 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 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
参考链接https://blog.csdn.net/lujiangui/article/details/107581007
参考链接https://www.cnblogs.com/han200113/p/11515327.html