当前位置 博文首页 > 程序猿学社的博客：【算法学习】 五 为什么要使用稀疏数组？
社长，一个爱学习，爱分享的程序猿，始终相信,付出总会有回报的。知识改变命运，学习成就未来。爱拼才会赢!
程序猿学社的GitHub，已整理成相关技术专刊，欢迎Star：。
https://github.com/ITfqyd/cxyxs
目录
前言
1. 简介
稀疏数据的记录方式：
2. 场景
3. 通过图更好的理解分析
实现逻辑
二维数组存储
稀疏数组存储方式
二维数组转稀疏数组的思路
稀疏数组转二维数组的思路
4实战
把数组循环输出
把二维数组转换成稀释数组
把稀疏数据保存为文件
把文件转为稀疏数组
把稀疏数组转为二维数组
稀疏数组(Sparse array) ，所谓稀疏数组就是数组中大部分的内容值都未被使用（或都为零），在数组中仅有少部分的空间使用。因此造成内存空间的浪费，为了节省内存空间，并且不影响数组中原有的内容值，我们可以采用一种压缩的方式来表示稀疏数组的内容。
适用于围棋，扫雷等等
?
五子棋，扫雷，跟我一个年代的社友，应该都经历过，以前小时候上信息课，教室是没有网络的，只能玩这些不用联网的小游戏。
社长发现，现在很多的游戏，都多了一个继续游戏的按钮。也就是说，就算你退出窗口后，还能从上一次的位置开始。他是怎么还能从上一次的位置开始的？
社长，就把这个问题，抛到朋友群里面。
隔壁小王说：社长，这个问题，很简单呀，就是通过二维数据存储。
大佬H说：二维数据效率太浪费空间了，假设白子为1，黑子为2，没有下的地方为0，我们可以发现很多的值都为0，建议使用稀疏数组保存，再生成文件，持久化到磁盘中。
?
?
?
?
假设9*9列棋盘，白子为1，黑子为2，没有下子位置为0
?
?
?
?
由99变成53，是不是节约了空间。
?
??/**
?????*?把数组循环输出
?????*/
????????public?static??void?printArray(int[][]?lists){
????????????//使用jdk1.8新特性?---第一种方法实现
????????????Arrays.stream(lists).forEach(i?->?{
????????????????Arrays.stream(i).forEach(n?->?System.out.printf("%d\t",?n));
????????????????System.out.println();
????????????});
????????????//或者使用for增强方式??---第二种方法实现
????????????/*for?(int[]?row?:?lists)?{
????????????????for?(int?item?:?row)?{
????????????????????System.out.printf("%d\t",??item);
????????????????}
????????????????System.out.println();
????????????}*/
????????}
注意：代码中使用jdk1.8的新特性,有两种方式可以实现
?/**
?????*?把二维数组转换成稀释数组
?????*?@param?lists
?????*?@return
?????*/
????public?static?int[][]?getSparseArray(int[][]?lists){
????????????if(lists.length?<?0){
????????????????System.out.println("二维数组的长度不能为空");
????????????????return?null;
????????????}
????????????//第一步：求出sum
????????????AtomicInteger?sum?=?new?AtomicInteger();//记录有多少个非0的有效数据
????????????//得到稀疏数组
????????????Arrays.stream(lists).forEach(i?->?{
????????????????Arrays.stream(i).filter(o?->?o!=0).forEach(n?->?sum.getAndIncrement());
????????????});
????????????//第二步：创建稀疏数组
????????????int?sparses?[][]?=?new?int?[sum.get()+1][3];
????????????//完成稀疏数组第一列
????????????sparses[0][0]?=?lists.length;?//行数
????????????sparses[0][1]?=?lists[0].length;??//列数
????????????sparses[0][2]?=?sum.get();
????????????int?count?=?0;
????????????for(int?x=0;x<sparses[0][0];x++){
????????????????for(int?y?=?0;y<sparses[0][1];y++){
????????????????????if(lists[x][y]?!=?0)?{
????????????????????????count+=1;
????????????????????????sparses[count][0]?=?x;
????????????????????????sparses[count][1]?=?y;
????????????????????????sparses[count][2]?=?lists[x][y];
????????????????????}
????????????????}
????????????}
????????????return?sparses;
????????};
AtomicInteger标识原子性，也就是多线程过程中i++，高并发，假设1000个线程，每个都调用一次i++，最终的结果应该是1000，但是，不好意思，最终的结果可能会小于1000。可以把该字段设置为AtomicInteger，最终的结果一定是1000.
第一步：求出sum
第二步：创建稀疏数组
第三步：把二维数组的行、列、有效数据，转为稀疏数组第一行的值。
第三步，依次把二维数据对应的行、列、值映射到稀疏数组中。
?/**
?????*?把稀疏数据保存为文件
?????*?@param?sparses
?????*?@param?path
?????*/
????public?static?void?sparseToFile(int[][]?sparses,?String?path){
????????FileWriter?fileWriter?=?null;
????????try?{
????????????File?file?=?new?File(path);
????????????if?(file.exists())?{??//存在
????????????????file.delete();??//则删除
????????????}
????????????//目录不存在?则创建
????????????if?(!file.getParentFile().exists())?{
????????????????boolean?mkdir?=?file.getParentFile().mkdirs();
????????????????if?(!mkdir)?{
????????????????????throw?new?RuntimeException("创建目标文件所在目录失败！");
????????????????}
????????????}
????????????file.createNewFile();
????????????fileWriter?=?new?FileWriter(path);
????????????for?(int[]?row?:?sparses)?{
????????????????for?(int?item?:?row)?{
????????????????????fileWriter.write(item+"\t");
????????????????}
????????????????//\r\n即为换行
????????????????fileWriter.write("\r\n");
????????????}
????????????//?把缓存区内容压入文件
????????????fileWriter.flush();
????????????System.out.println("稀疏数据保存文件成功!");
????????}?catch?(IOException?e)?{
????????????e.printStackTrace();
????????}finally?{
????????????if(fileWriter!=null){
????????????????try?{
????????????????????fileWriter.close();
????????????????}?catch?(IOException?e)?{
????????????????????e.printStackTrace();
????????????????}
????????????}
????????}
????}
第一步：文件存在，则删除，目录不存在，则创建
第二步：依次把稀疏数组的值按9\t9\t4\n的格式插入。
/**
?????*?把文件转为稀疏数组
?????*?@param?path
?????*?@return
?????*/
????public?static??int[][]?fileToSparse(String?path){
????????File?file?=?new?File(path);
????????if(!file.exists()){
????????????System.out.println("文件转稀疏数据失败，文件不能为空!");
????????????return?null;
????????}
????????BufferedReader?bufferedReader?=?null;
????????try?{
????????????bufferedReader?=?new?BufferedReader(new?FileReader(file));
????????????String?line?=?null;
????????????//缓存文件里面的值，再解析处理
????????????StringBuilder??sb?=?new?StringBuilder?();
????????????int?count?=?0;
????????????while((line?=?bufferedReader.readLine())!=null){
????????????????//System.out.println("行："+line);
????????????????sb.append(line+"\r\n");
????????????????count+=1;
????????????}
????????????//解析sb数据
????????????int?sparses[][]=new?int[count][3];
????????????String[]?splits?=?sb.toString().split("\r\n");
????????????//第一行记录的是?二维数据的行和列，有效数据长度，不为有效数据
???????????for?(int?i?=?0;?i?<?splits.length;?i++)?{
????????????????????String[]?temp?=?splits[i].split("\t");
????????????????????for(int?j=0;j<temp.length;j++){
????????????????????????sparses[i][j]?=?Integer.parseInt(temp[j]);
????????????????????}
????????????}
???????????return?sparses;
????????}?catch?(Exception?e)?{
????????????e.printStackTrace();
????????}finally?{
????????????if(bufferedReader!=null){
????????????????try?{
????????????????????bufferedReader.close();
????????????????????bufferedReader?=?null;
????????????????}?catch?(IOException?e)?{
????????????????????e.printStackTrace();
????????????????}
????????????}
????????}
????????return?null;
????}
第一步：判断文件是否存在，不存在则提示
第二步：读取文件的值，先缓存到StringBuilder,因为稀疏数组的长度，只能通过读取所有的行才能获取。
第三步：创建稀疏数组，稀疏数组的[行数+1][3] 列固定为3
第三步：依次缓存字符串按9\t\9\t4\n解析，把对应的写入稀疏数组中。
/**
?????*?把稀疏数组转为二维数组
?????*?@param?fileToSparse
?????*?@return
?????*/
????public?static?int[][]?sparseToArray(int[][]?fileToSparse){
????????int[][]?twoLists?=?new?int[fileToSparse[0][0]][fileToSparse[0][1]];
????????for?(int?i?=?1;i<fileToSparse.length;i++)?{
????????????twoLists[fileToSparse[i][0]][fileToSparse[i][1]]?=?fileToSparse[i][2];
????????}
????????return?twoLists;
????}
第一步：稀疏数组的[0][0]标识二维数组行 [0][1]二维数组列
第二步：创建二维数组
第三步：循环稀疏数组，依次稀疏数组放入二维数组中。
github源码
程序猿学社的GitHub，欢迎Star：
https://github.com/ITfqyd/cxyxs
觉得有用,可以点赞,关注,评论，留言四连发。
?
cs