稀疏数组

当一个数组中大部分元素为0，或者为同一值的数组时，我们可以用稀疏数组来保存该数组。在稀疏数组中，数组下标为[0]的第一行元素分别代表原始数组的行列数以及中的有效值（即非零值）的个数，再往下从稀疏数组第二行开始，每行的元素分别记录了各个有效值在原始数组中所在的位置以及有效值的值。如下图所示，例如下标为[1]的第二行中的元素表示记录了原始数组中array[0][3]=22,即原始数组中第一行第四个数为22。

image.png

稀疏数组的处理方法：
1.记录数组一共有几行几列，有多少个不同的值
2.把具有不同值的元素的行列以及值记录在一个小规模的数组中，从而缩小程序的规模。
3.我们把上图的例子6行7列变成了9行3列，稀疏数组固定都是3列。

实例：

image.png

我们把一个11x11的数组转换成稀疏数组

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;

    int sum=0;
    for (int i = 0; i < 11; i++) {
        for (int j = 0; j <11 ; j++) {
            if (array1[i][j]!=0){
                sum++;
            }
        }
    }
    int[][] sparseArray=new int[sum+1][3];
    sparseArray[0][0]=11;
    sparseArray[0][1]=11;
    sparseArray[0][2]=sum;

    int sparseCount=1;
    for (int i = 0; i < 11; i++) {
        for (int j = 0; j <11 ; j++) {
            if (array1[i][j]!=0){
               sparseArray[sparseCount][0]=i;
               sparseArray[sparseCount][1]=j;
               sparseArray[sparseCount][2]=array1[i][j];
               sparseCount++;
            }
        }
    }
    System.out.println("输出的稀疏数组为：");
    for (int i = 0; i < sparseArray.length; i++) {
        System.out.println(sparseArray[i][0]+"\t"+sparseArray[i][1]+"\t"+sparseArray[i][2]+"\t");
    }


}