稀疏数组

稀疏数组

当一个数组中大部分元素为0，或者为同一值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方式是:记录数组一共有几行几列，有多少个不同值；把具有不同值的元素和行列及值记录在一个小规模的数组中，从而缩小程序的规模
，为了节约空间起到压缩的效果，将数据用另一种结构来表示，即稀疏数组

形式

二维数组
0 0 0
0 1 0
0 0 0
0 0 0
稀疏数组
4 3 1
1 1 1

code

public class Test {

    public static void main(String[] args) throws IOException {
        int [][] arr = {{0,0,0},{0,1,0},{0,0,0},{0,0,0}};
        System.out.println("二维数组：");
        for(int i = 0; i < arr.length; i ++) {
            for(int j = 0; j < arr[i].length; j ++) {
                System.out.printf("%d\t", arr[i][j]);
            }
            System.out.println();
        }

        //创建稀疏数组
        int sum = 0;
        for(int i = 0; i < arr.length; i ++) {
            for(int j = 0; j < arr[i].length; j ++) {
                if(arr[i][j] != 0) {
                    sum ++;
                }
            }
        }

        int [][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = 4;
        sparseArr[0][1] = 3;
        sparseArr[0][2] = 1;

        int count = 0;
        for(int i = 0; i < arr.length; i ++) {
            for(int j = 0; j < arr[i].length; j ++) {
                if(arr[i][j] != 0) {
                    count ++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = arr[i][j];
                }
            }
        }

        System.out.println("二维数组转稀疏数组：");
        for(int i = 0; i < sparseArr.length; i ++) {
            for(int j = 0; j < sparseArr[i].length; j ++) {
                System.out.printf("%d\t", sparseArr[i][j]);
            }
            System.out.println();
        }

        //稀疏数组转二维数组
        int[][] newArr = new int[sparseArr[0][0]][sparseArr[0][1]];
        int count2 = sparseArr[0][2];

        for(int i = 1; i < sparseArr.length; i ++) {
            //将稀疏数组的有数据的，记录在二维数组
            newArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }

        //输出转换后二维数组
        System.out.println("稀疏数组转二维数组：");
        for(int i = 0; i < newArr.length; i ++) {
            for(int j = 0; j < newArr[i].length; j ++) {
                System.out.printf("%d\t", newArr[i][j]);
            }

            System.out.println();
        }


//        System.out.printf("%d\t", 1);
        System.out.println("读取文件稀疏数据");
        //读取文件稀疏数据
        int[][] ints = readFile();



    }

    //把稀疏数组存入本地文件txt
    public static void writeFile() {

    }
    //读取本地文件稀疏数组
    public static int[][] readFile() throws IOException {
//
        //模拟文件
        File file = new File("D:/sparseArr.txt");
        //将file转字符字符输入流
        FileInputStream fileInputStream = new FileInputStream(file);
        //将字符输入流转成buffer,可以逐行读
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(fileInputStream));

        //稀疏数组
        int cols = 3;
        int rows = 0;
        int sum = 0;
        //读取一行
        String content = bufferedReader.readLine();
        if(Strings.isNotBlank(content)) {
            String substring = content.substring(1, 2);
            String[] split = content.split(substring);
            rows = Integer.valueOf(split[0]);
            cols = Integer.valueOf(split[1]);
            sum = Integer.valueOf(split[2]);
        }
        System.out.printf("rows:%d,cols:%d,sum:%d\n", rows,cols, sum);

        //解析除了第一行，稀疏数组组装
        int[][] sparseArr = new int[sum + 1][cols];
        sparseArr[0][0] = rows;
        sparseArr[0][1] = cols;
        sparseArr[0][2] = sum;
        int count = 0;
        BufferedReader bufferedReader1 = new BufferedReader(new InputStreamReader(fileInputStream));
        String content2 = bufferedReader1.readLine();
        while (Strings.isNotBlank(content2)) {
            String substring = content2.substring(1, 2);
            String[] split = content2.split(substring);
            if(count >= 1) {//只处理第二行数据
                sparseArr[count][0] = Integer.valueOf(split[0]);
                sparseArr[count][1] = Integer.valueOf(split[1]);
                sparseArr[count][2] = Integer.valueOf(split[2]);
            }
            //读取下一行
            content2 = bufferedReader.readLine();
        }

        //打印解析后的稀疏数组
        System.out.println("打印解析后的稀疏数组：");
        for(int i = 0; i < sparseArr.length; i ++) {
            for(int j = 0; j < sparseArr[0].length; j ++) {
                System.out.printf("%d\t", sparseArr[i][j]);
            }
            System.out.println();
        }

//        int[][] sparseArr= new int[3][];

        
        return null;

    }
}

console

二维数组：
0   0   0   
0   1   0   
0   0   0   
0   0   0   
二维数组转稀疏数组：
4   3   1   
1   1   1   
稀疏数组转二维数组：
0   0   0   
0   1   0   
0   0   0   
0   0   0   
读取文件稀疏数据
rows:4,cols:3,sum:1
打印解析后的稀疏数组：
4   3   1   
0   0   0

场景

棋盘记录