稀疏数组

稀疏数组讲解

1.介绍

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

稀疏数组的处理方式：

1. 记录数组一共有几行几列，有多少个不同值。
2. 把具有不同值的元素和行列及值记录在一个小规模的数组中，从而缩小程序的规模。


2.示例

public class V6练习 {
    public static void main(String[] args) {

        System.out.println("原始数组:");
        //创建一个原始的二维数组,棋盘格  6*9
        int[][] a = new int[6][9];
        //定义四个有效值，随意放置
        a[4][5] = 8;
        a[3][7] = 7;
        a[1][8] = 10;
        a[2][4] = 11;
        //打印原始数组
        for (int i = 0; i < a.length; i++) { //输出行
            for (int j = 0; j < a[i].length; j++) { //输出列
                System.out.print(a[i][j] + "\t");
            }
            System.out.println(); //每输出一行，则换行输出
        }

        System.out.println("======================================");
        //根据原始的二维数组，创建稀疏数组
        System.out.println("稀疏数组:");

        //1.遍历原始二维数组，并保存有效值的个数
        int sum = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                if(a[i][j] != 0){
                    sum++; //由此计算出有效值个数
                }
            }
        }

        //2.创建一个新数组作为原始数组的稀疏数组
        int[][] b =new int[sum+1][3]; //稀疏数组的行数由原始数组的有效值决定，列数固定为3
        //稀疏数组的第一行是原始数组的行列数及有效值个数，第二行开始记录每个有效值的行列数及值
        b[0][0] = 6;
        b[0][1] = 9;
        b[0][2] = sum;
        //遍历原始数组，提取有效值的行列数，存放至稀疏数组
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[i].length; j++) {
                if(a[i][j] != 0){
                    count++; //累积有效值，从第二行开始存放，每一行记录一个有效值
                    b[count][0] = i;
                    b[count][1] = j;
                    b[count][2] = a[i][j];
                }
            }
        }

        //3.输出稀疏数组
        for (int i = 0; i < b.length; i++) {
            for (int j = 0; j < b[i].length; j++) {
                System.out.print(b[i][j] + "\t");
            }
            System.out.println();
        }

        System.out.println("======================================");
        //稀疏数组还原为二维数组
        System.out.println("还原数组:");

        //1.根据稀疏数组创建一个新数组
        int[][] c = new int[ b[0][0] ][ b[0][1] ]; //稀疏数组的第一行记录了二维数组的行列数及有效值

        //2.提取稀疏数组中有效值的行列数及值，放置到新数组中
        for (int i = 1; i < b.length; i++) {
            c[ b[i][0] ][ b[i][1] ] = b[i][2];
        }

        //3.输出新的二维数组
        for (int[] ints : c) { //使用for-each循环
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
    }
}