稀疏数组
基本介绍
稀疏数组可以看作是普通数组的压缩，当一个数组中大部分元素为0或同一个值时，可用稀疏数组来保存该数组
使用目的
- 源数组中存在大量的无效数据，占据了大量存储空间，真正有用的数据却很少
- 压缩存储可以有效地利用资源，避免资源的无效浪费，当数据序列化到磁盘时，压缩存储可以提高压缩效率
实现思路
1，稀疏数组的第一列表示原数组行数，第二列表示原数组列数，第三列表示值
2，第一行存放，原数组几行，几列，共有几个不一样的值
3，随后的每一行都存放的是特殊值的位置（行，列）及值
-
普通数组转稀疏数组：
<1>遍历原始二维数组得到有效数据（非0）的个数sum;
<2>根据sum（确定稀疏数组的大小）创建稀疏数组 ";
<3>将二维数组的有效数据存入稀疏数组>将二维数组的有效数据存入稀疏数组;
-
稀疏数组转普通数组：
<1>先读取稀疏数组的第一行，根据第一行来创建原始二维数组
<2>2，读取稀疏数组的后几行数据赋值给原始的二维数组
图解
代码实现
-
普通二维数组转稀疏数组：
/** * 普通数组转稀疏数组 * @param arr；传入普通二维数组 * @return：返回此二维数组对应的稀疏数组 */ public static int[][] transSpareArr(int[][] arr){ int sum=0;//sum：源数组中有效数据的个数 //循环遍历源数组获得源数组中有效数据的个数 for(int[] nums:arr){ for(int num:nums){ if(num!=0){ sum++; } } } int[][] sparArr=new int[3][sum+1];//创建稀疏数组 sparArr[0][0]=arr.length;//源数组有几行 sparArr[0][1]=arr[0].length;//源数组有几列 sparArr[0][2]=sum;//源数组有几个有效数据 int count=1;//用来记录是第几个非零数据 for(int i=0;i<arr.length;i++){ for(int j=0;j<arr[i].length;j++){ if(arr[i][j]!=0){ sparArr[count][0]=i;//第一列记录有效数据在源数组的所在行 sparArr[count][1]=j;//第二列记录有效数据在源数组的所在列 sparArr[count][2]=arr[i][j];//有效数据的值 count++; } } } return sparArr; } -
稀疏数组转普通二维数组：
/** * 稀疏数组转普通数组 * @param sparArr:传入稀疏数组 * @return：返回相对应的原数组 */ public static int[][] transArr(int[][] sparArr){ //根据稀疏数组的第0行数据创建源数组对象 // 稀疏数组第0行的第一列存储源数组共几行，稀疏数组第0行的第二列存储的是源数组共几列 int[][] arr=new int[sparArr[0][0]][sparArr[0][1]]; //遍历稀疏数组，将有效数据存入源数组相对应的位置 for(int i=1;i<sparArr.length;i++){ arr[sparArr[i][0]][sparArr[i][1]]=sparArr[i][2]; } return arr; }
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
