Day551.稀疏数组 -数据结构和算法Java

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

将左侧的二维数组 ，通过稀疏数组的方式，转变为右侧的数组结构

package com.achang.sparsearray;


public class SparseArray {

    public static void main(String[] args) {
        //创建一个二维数组 11*11
        //0代表没棋 1黑子 2白子
        int[][] originArr = new int[11][11];
        originArr[1][2] = 1;
        originArr[2][3] = 1;
        originArr[4][5] = 2;
        System.out.println("原始的二维数组");
        for (int[] ints : originArr) {
            for (int anInt : ints) {
                System.out.printf("%dt",anInt);
            }
            System.out.println();
        }

        //获取有效数字个数
        int sum = 0;
        for (int[] ints : originArr) {
            for (int anInt : ints) {
                if (anInt!=0){
                    sum++;
                }
            }
        }
        System.out.println(sum);

        //创建对应的稀疏数组
        int[][] sparseArray = new int[sum+1][3];
        sparseArray[0][0] = 11;
        sparseArray[0][1] = 11;
        sparseArray[0][2] = sum;

        //遍历原始二维数组，将有效数据，存储到稀疏数组中
        int count = 0;//用于记录是第几个非零数据
        for (int i = 0; i < originArr.length; i++) {
            for (int i1 = 0; i1 < originArr[i].length; i1++) {
                if (originArr[i][i1]!=0){
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = i1;
                    sparseArray[count][2] = originArr[i][i1];
                }
            }
        }
        System.out.println("===========");

        //输出稀疏数组
        for (int[] ints : sparseArray) {
            for (int anInt : ints) {
                System.out.printf("%dt",anInt);
            }
        }
        System.out.println("===========");

        //将稀疏数组恢复成二维数组
        int[][] originArr1 = new int[sparseArray[0][0]][sparseArray[0][1]];
        for (int i = 1; i < sparseArray.length; i++) {
            originArr1[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }

        for (int[] ints : originArr1) {
            for (int anInt : ints) {
                System.out.printf("%dt",anInt);
            }
            System.out.println();
        }

    }
}