# 稀疏数组

# 简介

稀疏数组是面对一个二维数组中有众多重复元素的情况下，为了节省磁盘空间，将此二维数组转化为更加节省空间的一种数组。如：
原始数组（11 * 11）：

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 0 2 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0

压缩后的稀疏数组：

row col val

11 11 2

1 2 1

2 4 2

第一行表示原数组有11行，11列表，非0数据有2个，接下来的行数表示第几行，第几列，非0数据值。
可以看到采用稀疏数组可以节省大量空间。

# Java实现


/**
 * @ClassName: SparseArray
 * @Description: 稀疏数组
 * @Author: pengl
 * @Date: 2020/5/7 12:54
 * @Version V1.0
 */
public final class SparseArray {
    /**
     * @MethodName: from
     * @Description: 将一个普通数组转换为稀疏数组
     * @Author: pengl
     * @Date: 2020/5/7 12:55
     * @Version V1.0
     */
    public static int[][] from(int[][] arr) {
        Assert.notNull(arr, "arr is null");
        int sum = 0;
        List<String> locations = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                int val = arr[i][j];
                if (val != 0) {
                    locations.add(i + "," + j + "," + val);
                    sum++;
                }
            }
        }

        int[][] result = new int[sum + 1][3];
        result[0] = new int[]{arr.length, arr[0].length, sum};
        if (locations.size() > 0) {
            for (int i = 0, len = locations.size(); i < len; i++) {
                String[] ss = locations.get(i).split(",");
                result[i + 1] = new int[]{Integer.parseInt(ss[0]), Integer.parseInt(ss[1]), Integer.parseInt(ss[2])};
            }
        }

        return result;
    }

    /**
     * @MethodName: to
     * @Description: 将一个稀疏数组还原成普通数组
     * @Author: pengl
     * @Date: 2020/5/7 12:56
     * @Version V1.0
     */
    public static int[][] to(int[][] arr) {
        Assert.notNull(arr, "arr is null");
        int[][] result = new int[arr[0][0]][arr[0][1]];
        for (int i = 1; i < arr.length; i++) {
            int[] row = arr[i];
            result[row[0]][row[1]] = row[2];
        }
        return result;
    }
}

# 测试

public class SparseArrayTest {
    @Test
    public void t1(){
        int[][] chessArr = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        //输出原始的二维数组
        System.out.println("原始的二维数组：");
        print(chessArr);
        //转换为稀疏数组
        int[][] sparseArr = SparseArray.from(chessArr);
        System.out.println("压缩后的稀疏数组：");
        print(sparseArr);

        System.out.println("解压稀疏数组：");
        print(SparseArray.to(sparseArr));
    }

    private void print(int[][] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j]+"\t");
            }
            System.out.println();
        }
    }
}

# 控制台打印

原始的二维数组：
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	
压缩后的稀疏数组：
11	11	2	
1	2	1	
2	3	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