稀疏数组

稀疏数组
稀疏数组介绍

当一个数组中大部分元素为0，或为同一值的数组时，可以使用稀疏数组来保存该数组。

稀疏数组的处理方式是：

记录数组一共有几行几列，有多少个不同值

把具有不同值的元素和行列及值记录在一个小规模的数组中，从而缩小程序的规模

public class arrayDemo9 {
    public static void main(String[] args) {
        int [][] array1 = new int[11][11];
        array1[9][2] = 1;
        array1[10][1] = 2;
        //获取有效值的个数
        int sum =getSum(array1);
        System.out.println("打印array1原始数组，array1数组的有效个数为:" + sum);
        printArrays(array1);
        System.out.println("打印保存array1数组中有效值的array2数组：");
        //创建一个稀疏数组的数组array2用于保存array1的有效数值,稀疏数组有行，列，值三列，所以创建稀疏数组是固定的第3列，行数=表头一行+实际的有效个数，所以是sum+1
        int [][] array2 = new int[sum + 1][3];
        saveArray1(array1,array2,sum);
        printArrays(array2);
        System.out.println("还原array2数组存入array3：");
        //创建array3数组用于存放array2还原的数据
        int [][] array3 = new int[array2[0][0]][array2[0][1]];
        reverseArray1(array2,array3);
        printArrays(array3);
    }
    public static int [][] saveArray1(int [][] array1,int [][] array2,int sum){
        //为稀疏数组的表头赋值，第一行存放array1数组的行，列，有效个数
        array2[0][0] = 11;
        array2[0][1] = 11;
        array2[0][2] = sum;
        //从array1数组中取到有效值存入array2中
        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];
                }
            }
        }
        return array2;
    }

    public static int getSum(int [][] array1){
        //转换为稀疏数组保存
        //获取有效值的个数
        int sum = 0;
        for (int i = 0; i < array1.length; i++) {
            for(int j = 0;j < array1[i].length;j++){
                if(array1[i][j] !=0){
                    sum ++;
                }
            }
        }
        return sum;
    }
    //array2还原存入array3
    public static int [][] reverseArray1(int [][] array2,int [][] array3){
        for (int i = 1; i < array2.length; i++) {
            array3[array2[i][0]][array2[i][1]] = array2[i][2];
        }
        return array3;
    }
    //打印二维数组
    public static void printArrays(int [][] arrays){
        for (int[] ints : arrays) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
    }
}