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

定义

稀疏数组是一种二维数组。当在二维数组中存在较多的无意义的数如0的时候，我们可以考虑采用稀疏数组以节省空间。稀疏数组是一种n行3列的二维数组，arr[i][0]表示行，arr[i][1]表示列,arr[i][2]表示该位置对应的值。在对应的稀疏数组的arr[0][i]中记录的是对应的总数据数。即总行数、总列数、总的记录值数。

举例

稀疏数组的处理方式是:记录数组一共有几行几列，有多少个不同值；把具有不同值的元，如下上面是原始数组，下面是稀疏数组

0 0 0 0 0 0 0  
0 0 1 0 0 0 0
0 0 0 2 0 0 0
0 0 0 0 0 4 0 
0 0 0 0 0 0 0
5 7 3
1 2 1
2 3 2
3 5 4

稀疏数组行数为原始数组中不为0的元素数目+1，列为3，第一行是用来存放原数组有多少行，多少列，总共多少个有效元素，假设原数组有效元素个数为sum，则稀疏数组可以定义为int[][] sparseArray = new int[sum+1][3]

sparseArray[0][0]表示原数组有多少行
sparseArray[0][1]表示原数组有多少列
sparseArray[0][2]表示原数组有多少个有效元素
sparseArray[i][0]，i>0表示第i个元素所在的行
sparseArray[i][1]，i>0表示第i个元素所在的列
sparseArray[i][1]，i>0表示第i个元素的值

这就是稀疏数组

Java版原始数组和稀疏数组的转换

public class SparseArray {
    public static void main(String[] args) {
        //稀疏数组和原数组的互相转化
        //1、初始化原数组
        int[][] array = new int[5][7];
        //2、设置值
        array[1][2]=1;
        array[2][3]=2;
        array[3][5]=4;
        //打印
        System.out.println("原始数组如下：");
        printArray(array);
        //因为原始数组太稀疏了，浪费空间，所以要转变为稀疏数组，转换步骤如下
        //我们先来构造第一行的值
        //1、获取原数组的行
        int rowSize  = array.length;
        //2、获取原数组的列
        int columnSize = array[0].length;
        //3、获取原数组的有效元素个数
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            int[] a = array[i];
            for (int j = 0; j < a.length; j++) {
                if(a[j]!=0) {
                    sum++;
                }
            }
        }
        //构造稀疏数组
        int[][] sparseArray = new int[sum+1][3];
        //第一行第一列表示原始数组的行
        sparseArray[0][0]=rowSize;
        //第一行第二列表示原始数组的列
        sparseArray[0][1]=columnSize;
        //第一行第三列表示原始数组有效数据的数目
        sparseArray[0][2]=sum;
        //设置稀疏数组的值,从第2行开始放元素，每放一个就换行
        int row = 0;
        for (int i = 0; i < array.length; i++) {
            int[] a = array[i];
            for (int j = 0; j < a.length; j++) {
                if(a[j]!=0) {
                    row++;
                    //这是一个值,从上到下来遍历
                    sparseArray[row][0] = i;
                    sparseArray[row][1] = j;
                    sparseArray[row][2] = a[j];
                }
            }
        }
        System.out.println("转换成稀疏数组如下：");
        printArray(sparseArray);
        //这里我们再来进行将稀疏数据转为原始数组，其实就是反向推到而已
        //1、获取数组有多少行
        int rowSizeBefore = sparseArray[0][0];
        int columnSizeBefore = sparseArray[0][1];
        //2、初始化数组
        int[][] arrayBefore = new int[rowSizeBefore][columnSizeBefore];
        //3、设置值
        for (int i = 1; i < sparseArray.length; i++) {
                arrayBefore[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        //还原后的数组
        System.out.println("还原后的数组：");
        printArray(arrayBefore);
    }
    /**
     * 打印数组
     * @param array
     */
    public static void printArray(int[][] array) {
        for (int i = 0; i < array.length; i++) {
            int[] a = array[i];
            for (int j = 0; j < a.length; j++) {
                System.out.print(a[j]+" ");
            }
            System.out.println();
        }
    }
}

结果如下

原始数组如下：
0 0 0 0 0 0 0 
0 0 1 0 0 0 0 
0 0 0 2 0 0 0 
0 0 0 0 0 4 0 
0 0 0 0 0 0 0 
转换成稀疏数组如下：
5 7 3 
1 2 1 
2 3 2 
3 5 4 
还原后的数组：
0 0 0 0 0 0 0 
0 0 1 0 0 0 0 
0 0 0 2 0 0 0 
0 0 0 0 0 4 0 
0 0 0 0 0 0 0