稀疏数组（Java代码实现）

有时候使用二维数组来保存数据的时候，会出现这种情况：

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
3 0 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 7

我们看见这种情况的数组有很多的相似的数据。在这50个数据中，除了其中的4的数据外（后面我们把这4个数字比喻做特殊数字），其他的全部都是0。
如果我们直接用二维数组来保存这些数据的话，就会花费很多的内存。所以我们需要用一种方式来将这个数组进行化简之后存储。

我们先来看一下化简之后的(稀疏)数组是什么样子：

5        10        4
1         5         1
2         0         3
3         3         2
4         9         7

经过化简之后，就从5 × 10 的数组变成了5 × 3的数组。要存储的数据也变成了15个。这大大减少了存放数据所占用的空间。

现在我们来解释一下转换后的数组每行每列的意义：

在转换后的第一行中，
5 10 4
这三个数，5代表原数组有5行，10代表原数组有10列，4则代表有4个数（因为其他的数字都是0，而这4个数都是不同与0的需要存储的数字）。这个4也同时定义了稀疏数组的大小。
稀疏数组的列是固定的，即col = 3，而行则是需要存放数字个数加一（算上存放原数组的信息）。拿这个例子来说，稀疏数组的大小应该是 sparseArray[5][3]
而在接下来的4行内容的性质都是一样的：需要存储的原数组中特殊信息。
例如这个第二行
1 5 1
1代表是这个特殊数字在整个数组的第1行，5代表是在第5列，1就是这个位置存放的那个数字。
类似这样以此往后。

接下来用代码来进行实现这个稀疏数组：

首先我们创建一个二维数组

    int[][] Array = new int[5][10];
    Array[1][5] = 1;
    Array[2][0] = 3;
    Array[3][3] = 2;
    Array[4][9] = 7;

然后需要对这个数组进行遍历，数出有多少个特殊数字

        int sum = 0;
        for (int i = 0; i < Array.length; i++) {
            for (int j = 0; j < Array[0].length; j++) {
                if (Array[i][j] != 0)
                    sum ++;
            }
        }

当我们知道了有多少个特殊数字之后，就可以创建稀疏数组了

        int[][] sparseArray = new int[sum + 1][3];

        sparseArray[0][0] = Array.length;
        sparseArray[0][1] = Array[0].length;
        sparseArray[0][2] = sum;

        int count = 0;
        for (int i = 0; i < Array.length; i++) {
            for (int j = 0; j < Array[0].length; j++) {
                if (Array[i][j] != 0){
                    count ++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = Array[i][j];
                }
            }
        }

然后我们可以将该数组输出看看结果如何

        for (int i = 0; i < sparseArray.length; i++) {
            for (int j = 0; j < sparseArray[i].length; j++) {
                System.out.printf("%d\t", sparseArray[i][j]);
            }
            System.out.println();
        }

除了将二维数组转化为稀疏数组之外，我们也需要在使用数组时把稀疏数组转化为二维数组：

首先获取稀疏数组第一行的信息来创建二维数组：

        int[][] sourceArray = new int[sparseArray[0][0]][sparseArray[0][1]];

然后将稀疏数组中的数据存放到创建的这个原数组中：

        for (int i = 1; i < sparseArray.length; i++) {
            sourceArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }