稀疏数组

稀疏数组

当数组出现大量空白时，用于节省空间

//稀疏数组的创建与使用
/*当二维数组中出现大量重复数字时，可以使用稀疏数组来压缩节省空间
布局为：
      行      列      值
[0]  总行数   总列数   有效值个数（除零外的数）
[1]  对应行   对应列    值
.
.
.
[有效值个数]
* */
public class SparseArray {
    public static void main(String[] args) {
        //先创建一个二维数组
        int[][] arr1 = new int[10][10];
        arr1[2][4] = 2;
        arr1[4][1] = 5;

        //打印出来二维数组

        //数组名.length 代表二维数组行数
        //数组名[0].length 代表二维数组列数
        //遍历打印的同时，计算有多少有效数
        int sum = 0;
        System.out.println("原数组：");
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr1[0].length; j++) {
                if(arr1[i][j] != 0){
                    sum += 1;
                }
                System.out.print(arr1[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("========");
        //创建稀疏数组
        int[][] arr2 = new int[sum+1][3];//行数为有效值个数+第一行（说明行）
        arr2[0][0] = arr1.length;//总行数
        arr2[0][1] = arr1[0].length;//总列数
        arr2[0][2] = sum;//有效值个数
        int count = 0;//重新定义记录数，来记录有效数个数
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr1[0].length; j++) {
                if (arr1[i][j] != 0) {
                    count++ ;
                    arr2[count][0]=i;//有效数出现所在行
                    arr2[count][1]=j;//有效数出现所在列
                    arr2[count][2]=arr1[i][j];//有效数值
                }
            }
        }
        //打印稀疏数组
        System.out.println("稀疏数组：");
        for (int i = 0; i < arr2.length; i++) {
            for (int j = 0; j < arr2[0].length; j++) {
                System.out.print(arr2[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("========");

        //运用稀疏数组还原
        int[][] arr3 = new int[arr2[0][0]][arr2[0][1]];
        for (int i = 1; i < arr2.length; i++) {//遍历稀疏数组每一行，因为就三列，所以列不遍历
            arr3[arr2[i][0]][arr2[i][1]] = arr2[i][2];
        }

        //打印还原的数组
        System.out.println("还原数组：");
        for (int i = 0; i < arr3.length; i++) {
            for (int j = 0; j < arr3[0].length; j++) {
                System.out.print(arr3[i][j]+" ");
            }
            System.out.println();
        }
    }
}