滚雪球学Java(32):如何理解和实现稀疏数组
🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,助你一臂之力,带你早日登顶🚀,欢迎大家关注&&收藏!持续更新中,up!up!up!!
前言
在实际开发中,我们常会遇到占用内存过大的问题,如何在规避内存浪费的情况下,存储大量数据是我们需要考虑的问题。本篇文章将介绍一种特殊的数据结构——稀疏数组,帮助开发者解决存储数据时占用内存过大的问题,提高程序的效率。
摘要
稀疏数组是一种特殊的二维数组,用于存储大量数据时占用内存过大的问题。稀疏数组的存储方式是将非零元素及其下标存储起来,其余元素均默认为0。本文将介绍稀疏数组的概念、实现方法以及测试用例,帮助读者更好地理解和应用稀疏数组。
稀疏数组
概念
稀疏数组是指大部分元素为0或者同一值的二维数组。在实际应用中,二维数组非零元素占比较小,而且同一值的元素会重复出现,这就导致了存储空间的浪费。例如,一个10000*10000的数组,只有100个元素是非零元素,其他的元素都是0,这样存储的话会占用非常大的存储空间。而使用稀疏数组可以有效地解决这个问题。
稀疏数组的存储方式是将二维数组的非零元素及其下标存储起来,其中第一行存储原始二维数组的行数、列数及非零元素个数;接下来每行都存储一个非零元素的行数、列数及值。
稀疏数组VS原始数组
稀疏数组是一种特殊的数组,它可以用来表示原始数组中大部分元素都是相同值的情况。稀疏数组可以节省存储空间,但也存在一些缺点。以下是稀疏数组对比原始数组的优缺点:
优点:
-
节省空间。稀疏数组只存储非零元素及其位置信息,而原始数组需要存储每个元素的数值和位置信息。
-
更快的存取速度。由于稀疏数组只存储非零元素及其位置信息,所以查找某个元素的时间更短。
缺点:
-
转换成稀疏数组需要额外的处理时间。如果原始数组中非零元素的数量相对较少,转换成稀疏数组需要花费一定的时间。
-
稀疏数组的处理不如原始数组灵活。原始数组可以直接进行大量的操作,而稀疏数组需要先转换成原始数组才能进行操作。
综上所述,稀疏数组在存储大规模数据时具有明显的优势,但在某些情况下,它的转换和处理可能会带来额外的时间和空间成本。
实现方法
下面我们来看一下如何通过Java代码实现稀疏数组。
创建原始二维数组
我们首先需要创建一个原始二维数组,这里以一个五子棋游戏的棋盘为例,创建一个11*11的二维数组,用于存储棋子的位置。其中,0表示没有棋子,1表示黑子,2表示白子。
int[][] chessBoard = new int[11][11];
chessBoard[1][2] = 1;
chessBoard[2][3] = 2;
// 输出原始二维数组
for (int[] row : chessBoard) {
for (int data : row) {
System.out.print(data + " ");
}
System.out.println();
}
输出结果:
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
将二维数组转为稀疏数组
我们需要将上面的二维数组转换为一个稀疏数组,实现代码如下:
int sum = 0;
for (int[] row : chessBoard) {
for (int data : row) {
if (data != 0) {
sum++;
}
}
}
int[][] sparseArray = new int[sum + 1][3];
sparseArray[0][0] = 11;
sparseArray[0][1] = 11;
sparseArray[0][2] = sum;
int count = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessBoard[i][j] != 0) {
count++;
sparseArray[count][0] = i;
sparseArray[count][1] = j;
sparseArray[count][2] = chessBoard[i][j];
}
}
}
// 输出稀疏数组
for (int[] row : sparseArray) {
for (int data : row) {
System.out.print(data + " ");
}
System.out.println();
}
输出结果:
11 11 2
1 2 1
2 3 2
可以看到,输出的结果是一个3*3的稀疏数组,第一行表示原始二维数组的行数、列数及非零元素个数,接下来的两行分别表示非零元素的位置及其值。
将稀疏数组转为原始二维数组
我们可以通过上面构造的稀疏数组,将其转换为原始二维数组,代码如下:
int[][] chessBoard2 = new int[sparseArray[0][0]][sparseArray[0][1]];
for (int i = 1; i < sparseArray.length; i++) {
chessBoard2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
}
// 输出转换后的原始二维数组
for (int[] row : chessBoard2) {
for (int data : row) {
System.out.print(data + " ");
}
System.out.println();
}
输出结果:
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
我们可以看到,转换后的原始二维数组与之前创建的二维数组完全一致。
附录源码
如上涉及所有源码均已上传同步在Gitee,提供给同学们一对一参考学习,辅助你更迅速的掌握。
☀️建议/推荐你
无论你是计算机专业的学生,还是对编程有兴趣的小伙伴,都建议直接毫无顾忌的学习此专栏「滚雪球学Java」,bug菌郑重承诺,凡是学习此专栏的同学,均能获取到所需的知识和技能,全网最快速入门Java编程,就像滚雪球一样,越滚越大,指数级提升。
📣关于我
我是bug菌,CSDN | 掘金 | infoQ | 51CTO 等社区博客专家,历届博客之星Top30,掘金年度人气作者Top40,51CTO年度博主Top12,华为云 | 阿里云| 腾讯云等社区优质创作者,全网粉丝合计15w+ ;硬核微信公众号「猿圈奇妙屋」,欢迎你的加入!免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板等海量资料。
![](https://res.hc-cdn.com/ecology/9.3.130/v2_resources\images\global\blog-dialog.png)
华为开发者空间发布
让每位开发者拥有一台云主机
- 点赞
- 收藏
- 关注作者
评论(0)