Java 稀疏数组

稀疏数组

• 当一个数组中大部分元素为0时，或者为同一值的数组时，可以使用稀疏数组来保存该数组。
• 稀疏数组的处理方式是：
  • 记录数组一共有几行几列，有多少个不同值
  • 把具有不同值的元素和行列及值记录在一个小规模的数组中，从而缩小程序的规模

下面对该原始数组进行压缩，求出其稀疏数组：

public static void main(String[] args) {
        //1. 创建一个二维数组 11*11   0：没有棋子  1：黑棋   2：白棋
        int[][] array1 = new int[11][11];
        array1[1][2] = 1;//对原始数组进行初始化
        array1[2][3] = 2;

        //输出原始数组
        System.out.println("输出原始的数组");

        //利用两次循环对数组进行遍历
        for (int[] ints : array1) {
            for (int anInt: ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();
        }
        System.out.println("=================");

        //输出稀疏数组

        //定义临时变量
        int sum = 0;

        //for循环遍历原始数组，找出不为零的数，并计算其个数
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array1[i].length; j++) {
                if (array1[i][j]!=0){
                    sum++;
            }
        }
            }
        System.out.println("有效个数的值："+sum);

        //对稀疏数组进行初始化定义
        int[][] array2 = new int[sum+1][3];//稀疏数组第 0 行是要记录原始数组的行列数，和有效值个数。有效值的坐标是从第 1 行开始记录的，所以行数要 +1，而稀疏数组的列数是固定为 3 的
        array2[0][0] = array1.length;//记录原始数组的行数
        array2[0][1] = array1[0].length;//记录原始数组的列数
        array2[0][2] = sum;//有效值个数

        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][2] = array1[i][j];
                    array2[count][1] = j;
                    array2[count][0] = i;
                    }
            }
        }

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

        //遍历打印稀疏数组
        for (int[] ints:array2) {
            for (int anInt:ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();
        }
        System.out.println("=================");
        
        //稀疏数组转化为原始数组输出
        System.out.println("稀疏数组转换为原始数组");
        
        //初始化原始数组
        int[][] array3 = new int[array2[0][0]][array2[0][1]];

        //遍历稀疏数组，获取有效值原坐标，填充回原始数组
        for (int i = 1; i < array2.length; i++) {//稀疏数组第 1 行才开始记录有效值的坐标，所以要从第 1 行开始遍历
           array3[array2[i][0]][array2[i][1]]=array2[i][2];
           }

        System.out.println("原始数组");
        for (int[] ints:array3) {
            for (int anInt:ints) {
                System.out.print(anInt+"\t");
            }
            System.out.println();
        }
        }