Java的稀疏数组的简单代码实现

Java的稀疏数组的简单代码实现

一、稀疏数组的基本概念

当二维数组的很多值是默认值 0,或者有很多相同的值时，记录了很多没有意义的数据，因此，在这里，我们需要引入一个新的概念——稀疏数组

在稀疏数组中，每行分别有三个元素：行，列，值。在稀疏数组的第一行，行表示原数组的行数，列表示原数组的列数，值表示原数组非0数据的个数；接下来的稀疏数组的几行中，行表示非0数据所在原数组的行数，列表示非0数据所在原数组的列数，而值则代表此非0数据的值。

如下面这个数组：

0 0 0 2 0

0 0 0 0 0

0 1 0 0 0

0 0 0 0 0

用稀疏数组表示为：

5 5 2 （表示原始数组有4行7列，有2个非0的值）

0 3 2 （表示在原始数组的下标为0的行、下标为3的列上有值为2，即在原始数组的1行4列上是2）

3 1 1 （表示在原始数组的下标为3的行、下标为1的列上有值为1，即在原始数组的4行2列上是1）

与原数组相比，稀疏数组变小了很多，原始数组有25个元素，而用稀疏数组表示则只有9个元素。

二、稀疏数组的Java代码实现思路

求出原始数组中非0的值的个数
创建二维数组，稀疏数组的第一行分别为原始数组的行数、列数、非0值的个数
利用for循环找出原始数组中非0值以及非0值的行标和列标，从稀疏数组第二行开始就是原始数组的非0值的坐标，第一列是非0值在原始数组中的下标行数，第二列就是非0值在原始数组中的下标列数，第三列就是非0值

三、稀释数组的Java代码实现

package array;

/*

    实现java的稀疏数组

 */

public class arrayDemo_01 {

    /*

        原数组 5*5    有效值 2

        0 0 0 2 0

        0 0 0 0 0

        0 0 0 0 0

        0 1 0 0 0

        0 0 0 0 0

        可以看出原数组中除了2个值外，其他的都是0

        稀疏数组

        5 5 2

        0 3 2

        3 1 1

     */

    //因为代码中多次出现for循环，所以定义遍历traversal方法

    public static int traversal(int[][] array) {

        int sum = 0;

        for (int[] ints : array) {

            for (int anInt : ints) {

                System.out.print(anInt + "\t");	//打印数组

                if (anInt != 0) {

                    sum++;	//获取非零值的个数

                }

            }

            System.out.println();

        }

        return sum;

    }

    public static void main(String[] args) {

        //原始数组

        int[][] array1 = new int[5][5];

        array1[0][3] = 2;

        array1[3][1] = 1;

        //输出原始数组

        System.out.println("\t\t\t原始数组");

        //获取有效值的个数,同时输出原始数组

        int sum = traversal(array1);

        System.out.println();

        System.out.println("==================================");

        System.out.println();

        //转化为稀疏数组保存

        //创建一个稀疏数组的数组

        int[][] array2 = new int[sum + 1][3];

        array2[0][0] = 5;

        array2[0][1] = 5;

        array2[0][2] = 2;

        int count = 0;   //充当稀疏数组的行

        for (int i = 0; i < array1.length; i++) {

            for (int j = 0; j < array1[i].length; j++) {

                if (array1[i][j] != 0) {

                    count++;

                    array2[count][0] = i; //稀疏数组第一列为原始数组的行

                    array2[count][1] = j; //稀疏数组第二列为原始数组的列

                    array2[count][2] = array1[i][j];  //稀疏数组第三列为原始数组非零值

                }

            }

        }

        System.out.println("有效值：" + count);

        //输出稀疏数组

        System.out.println(" 稀疏数组");

        for (int[] ints : array2) {

            System.out.println(ints[0] + "\t"

                    + ints[1] + "\t"

                    + ints[2] + "\t");

        }

        System.out.println("====================");

        System.out.println("还原");

        //读取稀疏数组，创建数组

        int[][] array3 = new int[array2[0][0]][array2[0][1]];

        //还原其他的值

        for (int i = 1; i < array2.length; i++) {

            array3[array2[i][0]][array2[i][1]] = array2[i][2];

        }

        //打印还原后的数组

        System.out.println("\t\t 还原后的数组");

        traversal(array3);

    }

}

四、结语

在运用稀疏数组时，不一定要是0值，其他值占大多数时也可以用稀疏数组。

本文是本人在学习过程中的笔记分享，欢迎大家指正批评，同时也希望能够帮助到需要的人！

巴特西

Java的稀疏数组的简单代码实现

Java的稀疏数组的简单代码实现

一、稀疏数组的基本概念

二、稀疏数组的Java代码实现思路

三、稀释数组的Java代码实现

四、结语

最新文章

热门文章