二维数组与稀疏数组的互相转换

二维数组的定义：本质上是以数组为数组元素的数组，即 数组的数组

稀疏数组的诞生的大概背景：在传统的二维数组存储方式，会利用大量的存储空间来存放0值（即默认值为0），从而浪费大量内存，进行存储时会浪费比较大的空间。

稀疏数组的定义：通过一个三元组的方式将非0数据保存到一个数组中。

代码实现(Java代码)

        // 创建一个二维数组 6 * 6
        // 在二维数组中存放三个数据
        int[][] array = new int[6][6];
        // 第2行第6列存放一个为66的数据
        array[1][5] = 66;
        // 第3行第3列存放一个为 99
        array[2][2] = 99;
        // 第6行第3列存放一个为88的数据
        array[5][2] = 88;

输出 二维数组的数据

        for (int[] row : array) {
            for (int data : row) {
                System.out.print(data + "\t");
            }
            System.out.println();
        }

二维数组 转 稀疏数组
创建一个稀疏数组需要的条件
1）遍历二维数组，获取到 有效数据的个数（sum）
2）根据sum创建 稀疏数组 sparse int[ sum + 1 ][ 3 ]

        // 获取有效数据的个数
        int sum = 0;
        for (int[] row : array) {
            for (int data : row) {
                if( data != 0 ){
                    sum ++;
                }
            }
        }
        System.out.println("二维数组中有效的数据个数为：" + sum); 
       // 结果为：sum = 3

创建 稀疏数组

       // 根据sum创建 稀疏数组
        int [][] sparse = new int[sum + 1][3];

稀疏数组的第一行存储二维数组的 行 与 列 和 有效数据的个数

        // 第一行存放 二维数组的行与列和有效数据的个数
        sparse[0][0] = array.length; sparse[0][1] = array[0].length; sparse[0][2] = sum;

稀疏数组的第N行（N != 0 && N > 0 ）存储 有效数据 在二维数组中的位置

        // 用于记录
        int count = 0;
        // row
        for (int i = 0; i < array.length; i++) {
            // data
            for (int j = 0; j < array[i].length; j++) {
                if( array[i][j] != 0 ){
                    count ++;
                    sparse[count][0] = i;
                    sparse[count][1] = j;
                    sparse[count][2] = array[i][j];
                }
            }
        }

输出 稀疏数组的数据

二维数组数据 与 稀疏数组数据进行校验

image.png

稀疏数组 转 二维数组

// 根据 稀疏数组的第一行 存储二维数组的行数与列数来创建一个新的二维数组
int [][] array2 = new int[sparse[0][0]][sparse[0][1]];

将稀疏数组的第N行（N != 0 && N > 0 ）存储的有效数据 赋值给 array2 二维数组

        // row
        for (int i = 1; i < sparse.length; i++) {
            // data
            for (int j = 0; j < sparse[i].length; j++) {
                array2[sparse[i][0]][sparse[i][1]] = sparse[i][j];
            }
        }

输出 二维数组 array2 的数据

        for (int[] row : array2) {
            for (int data : row) {
                System.out.print(data + "\t");
            }
            System.out.println();
        }

本次案例的完整案例代码如下：

  // 创建一个二维数组 6 * 6
        // 在二维数组中存放两个数据
        int[][] array = new int[6][6];
        // 第2行第6列存放一个为66的数据
        array[1][5] = 66;
        // 第3行第3列存放一个为 99
        array[2][2] = 99;
        // 第6行第3列存放一个为88的数据
        array[5][2] = 88;
        //输出
        // 记录二维数组中有几个有效的数值
        int sum = 0;
        for (int[] row : array) {
            for (int data : row) {
                System.out.print(data + "\t");
                if( data != 0 ){
                    sum ++;
                }
            }
            System.out.println();
        }
        System.out.println();
        System.out.println("二维数组中有效的数据个数为：" + sum);

        // 创建一个 稀疏数组 的前提条件（需要知道二维数组中有效的数据个数）
        // 1、遍历二维数组，获取到有效数据的个数（sum）
        // 2、根据sum创建 稀疏数组
        int [][] sparse = new int[sum + 1][3];
        // 第一行存放 二维数组的行与列和有效数据的个数
        sparse[0][0] = array.length;sparse[0][1] = array[0].length;sparse[0][2] = sum;
        // 用于记录
        int count = 0;
        // row
        for (int i = 0; i < array.length; i++) {
            // data
            for (int j = 0; j < array[i].length; j++) {
                if( array[i][j] != 0 ){
                    count ++;
                    sparse[count][0] = i;
                    sparse[count][1] = j;
                    sparse[count][2] = array[i][j];
                }
            }
        }
        // 输出 稀疏数组
        for (int[] ros : sparse) {
            for (int data : ros) {
                System.out.print(data + "\t");
            }
            System.out.println();
        }

        System.out.println();
        System.out.println();

        // 稀疏数组转二维数组
        int [][] array2 = new int[sparse[0][0]][sparse[0][1]];
        // row
        for (int i = 1; i < sparse.length; i++) {
            // data
            for (int j = 0; j < sparse[i].length; j++) {
                array2[sparse[i][0]][sparse[i][1]] = sparse[i][j];
            }
        }
        // 输出二维数组
        for (int[] row : array2) {
            for (int data : row) {
                System.out.print(data + "\t");
            }
            System.out.println();
        }