稀疏数组
2020-04-06 16:05:41来源:博客园 阅读 ()
稀疏数组
稀疏数组
介绍
当我们在处理如五子棋这类棋盘问题时,只有棋盘中的黑子和白字位置对于我们来说是由具体意义的,当一个二维数组中的绝大多数值都是某一个值时,我们选定位默认值,我们可以使用稀疏数组来保存,以达到节约空间的目的
处理过程
- 创建一个n+1行3列的二维数组(n为待压缩数组中不同于选定默认值的个数)
- 在第一行分别保存待压缩数组的行数、列数、n
- 对每一个不同于默认值的值按照行号、列号、值记录一行
把一个二维数组压缩为稀疏数组
public class SparseArray {
public int[][] array2SparseArray(int[][] res){
int n=0;
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[i].length;j++) {
if(res[i][j]!=0) {
n++;
}
}
}
int[][] tar=new int[n+1][3];
tar[0][0]=res.length;
tar[0][1]=res[0].length;
tar[0][2]=n;
int row=1;
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[i].length;j++) {
if(res[i][j]!=0) {
tar[row][0]=i;
tar[row][1]=j;
tar[row][2]=res[i][j];
row++;
}
}
}
return tar;
}
public static void main(String[] args) {
int[][] res=new int[4][5];
res[1][2]=1;
res[0][3]=2;
res[2][0]=1;
res[2][2]=1;
SparseArray sa=new SparseArray();
sa.print(res);
int[][] tar = sa.array2SparseArray(res);
sa.print(tar);
}
public void print(int[][] res) {
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[i].length;j++) {
System.out.print(res[i][j]+" ");
}
System.out.println();
}
}
}
输出:
0 0 0 2 0
0 0 1 0 0
1 0 1 0 0
0 0 0 0 0
4 5 4
0 3 2
1 2 1
2 0 1
2 2 1
把稀疏数组还原
public class SparseArray {
public int[][] array2SparseArray(int[][] res){
int n=0;
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[i].length;j++) {
if(res[i][j]!=0) {
n++;
}
}
}
int[][] tar=new int[n+1][3];
tar[0][0]=res.length;
tar[0][1]=res[0].length;
tar[0][2]=n;
int row=1;
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[i].length;j++) {
if(res[i][j]!=0) {
tar[row][0]=i;
tar[row][1]=j;
tar[row][2]=res[i][j];
row++;
}
}
}
return tar;
}
public int[][] sparseArray2Array(int[][] res){
int rows=res[0][0];
int cols=res[0][1];
int n=res[0][2];
int[][] tar=new int[rows][cols];
for(int i=1;i<=n;i++) {
int row=res[i][0];
int col=res[i][1];
int val=res[i][2];
tar[row][col]=val;
}
return tar;
}
public static void main(String[] args) {
int[][] res=new int[4][5];
res[1][2]=1;
res[0][3]=2;
res[2][0]=1;
res[2][2]=1;
SparseArray sa=new SparseArray();
sa.print(res);
int[][] tar = sa.array2SparseArray(res);
sa.print(tar);
int[][] res2 = sa.sparseArray2Array(tar);
sa.print(res2);
}
public void print(int[][] res) {
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[i].length;j++) {
System.out.print(res[i][j]+" ");
}
System.out.println();
}
}
}
输出:
0 0 0 2 0
0 0 1 0 0
1 0 1 0 0
0 0 0 0 0
4 5 4
0 3 2
1 2 1
2 0 1
2 2 1
0 0 0 2 0
0 0 1 0 0
1 0 1 0 0
0 0 0 0 0
原文链接:https://www.cnblogs.com/moyuduo/p/12650185.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:MySQL 学习笔记
下一篇:SSM第一天 springDI
- Java笔记:数组,异常,泛型 2020-06-08
- 数组小Demo 2020-05-25
- 从零开始的数组,这么设计么是为什呢? 2020-05-24
- LeetCode 面试题53 - I. 在排序数组中查找数字 I 2020-05-22
- LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash