数组 - 稀疏数组

￡神魔★判官ぃ 2022-11-09 11:27 221阅读 0赞

# **1.定义** #

稀疏数组可以看做是普通数组的压缩，但是这里说的普通数组是值无效数据量远大于有效数据量的数组

例如：

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

其稀疏数组形式：

11  11  2
    1   2   1
    2   4   2

# 2.使用场景 #

*  原数组中存在大量的无效数据，占据了大量的存储空间，真正有用的数据却少之又少
 *  压缩存储可以节省存储空间以避免资源的不必要的浪费，在数据序列化到磁盘时，压缩存储可以提高IO效率

# 3.存储方式 #

第一行存储原始数据总行数，总列数，总的有效数据个数

接下来每一行都存储非0数所在行，所在列，和具体值

rows cols val
    r1   c1   val1
    r2   c2   val2
    .    .     .
    .    .     .
    rn   cn   valn

# 4.代码实现 #

public class SparseArray {
        
        public static void main(String[] args) {
        
            int rows = 11;
            int cols = 11;
            int[][] chessArr1 = new int[rows][cols];
            chessArr1[1][2] = 1;
            chessArr1[2][3] = 2;
            printTwoDimensionalArray("原始的二位数组", chessArr1);
            //将二位数组转换为稀疏数组
            //1.先遍历二位数组 得到非0数据的个数
            int sum = 0;
            for (int i = 0; i < rows; i++) {
        
                for (int j = 0; j < cols; j++) {
        
                    if (chessArr1[i][j] != 0) {
        
                        sum++;
                    }
                }
            }
            //2.创建对应的稀疏数组
            int[][] sparseArr = new int[sum + 1][3];
            //给稀疏数组赋值
            sparseArr[0][0] = rows;
            sparseArr[0][1] = cols;
            sparseArr[0][2] = sum;
            //遍历二维数组，将非0的值存放到sparseArr
            int count = 1; //用于记录是第几个非0数组
            for (int i = 1; i < rows; i++) {
        
                for (int j = 0; j < cols; j++) {
        
                    if (chessArr1[i][j] != 0) {
        
                        sparseArr[count][0] = i;
                        sparseArr[count][1] = j;
                        sparseArr[count][2] = chessArr1[i][j];
                        count++;
                    }
                }
            }
            //输出稀疏数组
            printTwoDimensionalArray("得到的稀疏数组为~~~~", sparseArr);
    
            //稀疏数组转原始的二维数组
            int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
            for (int i = 1; i < sparseArr.length; i++) {
        
                chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
            }
            printTwoDimensionalArray("输出恢复后的二维数组", chessArr2);
        }
    
        /**
         * 打印int二维数组方法
         * @param name 输出名称
         * @param array 二维数组
         */
        public static void printTwoDimensionalArray(String name, int[][] array) {
        
            System.out.println(name);
            for (int[] row : array) {
        
                for (int data : row) {
        
                    System.out.printf("%d\t", data);
                }
                System.out.println();
            }
            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	
    
    得到的稀疏数组为~~~~
    11	11	2	
    1	2	1	
    2	3	2	
    
    输出恢复后的二维数组
    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