[数据结构与算法]入门稀疏数组（java）

我们可以把一个无效数据量远大于有效数据量的数组转化为（也可以说压缩为）稀疏数组。

例如 ：

//1.创建一个二位数组
int[][] array1 = new int[11][11]; //创建一个11行，11列的二维数组
array1[1][2] = 1; //把第2行，第3个元素的值赋为1
array1[2][3] = 2; //把第3行，第4个元素的值赋为2

0	0	0	0	0	0	0	0	0	0	0	
0	0	1	0	0	0	0	0	0	0	0	
0	0	0	2	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0

压缩后：

    行  列  值
[0] 11	11	2 //这一行代表，在11行，11列这个二维数组中，有两个有效值（非0值）
[1] 1	2	1 //第一个值的位置
[2] 2	3	2 //第二个值的位置	

如何将数组转化为稀疏数组

首先我们要获取原数组中有效值的个数：

int sum = 0;
for (int i = 0; i<11; i++){
    for(int j = 0; j<11; j++){
        if(array1[i][j]!=0){  //遇到一个非零的值，sum就+1
            sum++;
        }
    }
}

接下来让我们创建一个稀疏数组：

int[][] array2 = new int[sum+1][3]; //有效值个数+1就是稀疏数组的行数

array2[0][0] = 11; //先给第一行赋值
array2[0][1] = 11;
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][0] = i;  //原数组的行
            array2[count][1] = j;  //原数组的列
            array2[count][2] = array1[i][j];  //原数组中的值
        }
    }
}

输出稀疏数组：

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

System.out.println("===另一种方法===");

System.out.println("稀疏数组");
for(int i=0; i< array2.length; i++){
    System.out.println(array2[i][0] + "\t"
                      +array2[i][1] + "\t"
                      +array2[i][2] + "\t");
}

?如何将稀疏数组还原

创建一个数组，素组的大小就是稀疏数组中记录的值

//创建一个数组，素组的大小就是稀疏数组中记录的值
int[][] array3 = new int[array2[0][0]][array2[0][1]];

2.给其中的元素还原它的值

 //给其中的元素还原它的值
for (int i=1; i < array2.length; i++){ //稀疏数组中从第二行才开始记录具体的有效值，所以i=1
    array3[array2[i][0]][array2[i][1]] = array2[i][2];
}