假如现在有一个10*10的二维数组:

    1. 0 1 2 3 4 5 6 7 8 9
    2. 0[0,0,0,0,0,0,0,0,0,0]
    3. 1[0,0,0,1,0,0,0,0,0,0]
    4. 2[0,0,0,2,0,0,0,0,0,0]
    5. 3[0,0,2,0,0,0,0,0,0,0]
    6. 4[0,0,0,0,0,0,0,0,0,0]
    7. 5[0,0,0,0,0,0,0,0,0,0]
    8. 6[0,0,0,0,0,0,0,0,0,0]
    9. 7[0,0,0,0,0,0,0,0,0,0]
    10. 8[0,0,0,0,0,0,0,0,0,0]
    11. 9[0,0,0,0,0,0,0,0,0,0]

    数组中只存在少部分的有效数据,其余极大部分元素都是无效数据,如果我们直接存储这种数据,会造成很大程度的空间浪费,所以现在我们要用一种新的方式去存储这些原数组中的有效数据,那就是稀疏数组。
    稀疏数组,就是利用一种规定好的方式去存储原数组中的有效数据,我们在定义一个元素的时候,通常是定义他的三要素,即
    所以我们定义一个二维数组,这个二维数组只用来记录原数组的位置信息,以及该位置上对应的值。我们将这个数组定义成n+13列,n代表的是原数组中有效元素的个数。
    我们将每一行记录为。我们用第一行来记录原数组的总行数总列数元素个数

       0, 1, 2
    0[10,10, 3]
    1[ 1, 3, 1]
    2[ 2, 3, 2]
    3[ 3, 2, 2]
    

    如上所示:原来的1010的二维数组就被压缩成了43的稀疏数组,这个数组中的每一个值都是有效值,极大的减少了存储空间。爆赞!!
    现在我们来使用java实现将一个普通的二维数组转化为稀疏数组吧:

    /**
         * 原始的二维数组转化为稀疏数组
         * @param array 原始数组
         * @return 稀疏数组
         */
        public int[][] toSparse(int[][] array){
            //首先需要统计有效元素个数
            int count = 0;
            for (int i = 0; i < array.length; i++) {
                for (int j = 0; j < array.length; j++) {
                    if(array[i][j] != 0){
                        count++;
                    }
                }
            }
            //定义一个稀疏数组,n+1行,3列(n代表有效元素个数)
            //其中,第一行存储总共有几行,几列,有效元素总个数
            int[][] sparseArray = new int[count+1][3];
            sparseArray[0][0] = array.length;
            sparseArray[0][1] = array.length;
            sparseArray[0][2] = count;
            //找到原数组中的有效元素,将其存储到稀疏数组中
            int index = 0;
            for (int i = 0; i < array.length; i++) {
                for (int j = 0; j < array.length; j++) {
                   if(array[i][j] != 0){
                       //从第二行开始
                       index++;
                       sparseArray[index][0] = i;
                       sparseArray[index][1] = j;
                       sparseArray[index][2] = array[i][j];
                   }
                }
            }
            return sparseArray;
        }
    

    那么怎么将一个稀疏数组还原成原来的二维数组呢?

        /**
         * 稀疏数组恢复成原来的二维数组
         * @param sparseArray 稀疏数组
         * @return 二维数组
         */
        public int[][] restoreArray(int[][] sparseArray){
            //首先拿到稀疏数组后根据数组的第一行的信息创建数组大小
            int[][] array = new int[sparseArray[0][0]][sparseArray[0][1]];
            //根据数组的每一行的信息将有效元素放置在数组的相应位置
            for (int i = 1; i < sparseArray.length; i++) {
                for (int j = 0; j < sparseArray[0][2]; j++) {
                    int rows = sparseArray[i][0];
                    int column = sparseArray[i][1];
                    int value = sparseArray[i][2];
                    array[rows][column] = value;
                }
            }
            return array;
        }