稀疏数组
一、介绍
稀疏数组可以看作是普通数组的压缩，当一个数组中大部分元素为0或同一个值时，可用稀疏数组来保存该数组。
由此可以发现，当一个数组上出现大量无用的数组时，我们可以使用一些方法将其压缩成稀疏数组进行存储，等到使用的时候再进行解压还原。
最经典的案例便是五子棋了，如果要实现退回，保存当前五子棋进度，加载五子棋进度的时候，原先的数组就会显得臃肿，这时候稀疏数组就可以派上用场了。
稀疏数组的压缩方法：
- 记录原数组的大小，几行几列，以及有多少个不同的值
- 记录原数组不同的值的行数和列数，将其保存在一个小的数组之中
二、实现
1）思路分析
如果原始数组是11*11的一个二维数组，里面的有效值个数有三个，
那么转为稀疏数组后，将会变成一个4*3的稀疏数组。
如下图所示
转换前 | 转换后 |
|---|---|
https://banmoon-pic.oss-cn-guangzhou.aliyuncs.com/images/20221218175536.png https://banmoon-pic.oss-cn-guangzhou.aliyuncs.com/images/20221218175543.png
那么转换后的稀疏数组代表着什么呢，如下图所示
由此可以分析出来，将二维数组转换成为稀疏数组只需要这么几步就可以成功。
- 遍历原数组，得到原数组中有效值的个数
num - 创建一个稀疏数组，大小为
(num 1)*3 - 稀疏数组的第0行存放，原数组的行个数，列个数，以及有效值的个数
- 将有效值的行、列、值转换写入稀疏数组中
还原不多说了，也很简单的，直接看代码吧
2）代码实现
代码语言：javascript复制package com.banmoon.datastructure.SparseArray;
import java.util.Arrays;
/**
* 稀疏数组
*
* @author banmoon
*/
public class SparseArray {
public static void main(String[] args) {
int[][] arrays = new int[11][11];
arrays[2][3] = 1;
arrays[2][4] = 2;
arrays[3][3] = 1;
for (int[] array : arrays) {
System.out.println(Arrays.toString(array));
}
// 转换为稀疏数组
System.out.println("================ 分割线 ================");
int[][] sparseArray = generateSparseArray(arrays);
for (int[] ints : sparseArray) {
System.out.println(Arrays.toString(ints));
}
// 还原为原始数组
System.out.println("================ 分割线 ================");
int[][] originArray = restoreSparseArray(sparseArray);
for (int[] ints : originArray) {
System.out.println(Arrays.toString(ints));
}
}
/**
* 生成稀疏数组
* @param originArray 原始数组
* @return 稀疏数组
*/
public static int[][] generateSparseArray(int[][] originArray) {
// 得到原始数组的行个数、列个数
int row = originArray.length;
int col = originArray[0].length;
// 得到原始数组的有效值个数
int num = 0;
for (int[] ints : originArray) {
for (int j = 0; j < col; j ) {
if (ints[j] != 0) {
num ;
}
}
}
// 创建稀疏数组，并设置第0行的数据
int[][] sparseArray = new int[num 1][3];
sparseArray[0][0] = row;
sparseArray[0][1] = col;
sparseArray[0][2] = num;
// 将剩余的有效值压缩至稀疏数组
int currentRow = 1;
for (int i = 0; i < row; i ) {
for (int j = 0; j < col; j ) {
if (originArray[i][j] != 0) {
sparseArray[currentRow][0] = i;
sparseArray[currentRow][1] = j;
sparseArray[currentRow][2] = originArray[i][j];
currentRow ;
}
}
}
return sparseArray;
}
/**
* 还原稀疏数组
* @param sparseArray 稀疏数组
* @return 原始数组
*/
public static int[][] restoreSparseArray(int[][] sparseArray) {
int row = sparseArray[0][0];
int col = sparseArray[0][1];
// 创建原始数组
int[][] originArray = new int[row][col];
// 写入有效值
for (int i = 1; i < sparseArray.length; i ) {
int r = sparseArray[i][0];
int c = sparseArray[i][1];
int val = sparseArray[i][2];
originArray[r][c] = val;
}
return originArray;
}
}三、最后
数据结构正是我薄弱的地方，在这一方面正好重新开始进行学习。
我是半月，你我一同共勉！！！
