一、什么是稀疏数组

我们以五子棋游戏的存盘功能为例。先看下面的棋盘

上面的棋盘只下了几手，现在要对其进行保存，下次再从这里开始下。
我们分析该棋盘是一个 15*15的二维数组，其中未下子的格子在数组中的值用0表示，下白子的格子在数组中用1表示，下黑子的格子在数组中用2表示。
转换为数组则是下面这样：

我们发现该数组绝大部分元素的值都是0，只有极少部分的元素的值不为0。如果直接把这个数组所有元素都保存的话，需求保存 15 * 15 = 225 个元素。值为0的元素能否不存呢？在使用的时候再恢复为0。
稀疏数组就是为了解决这类问题的。
我们来分析下上面原始数组的一些有意义的信息：

1. 原始数组的行是 15
2. 原始数组的列是 15
3. 原始数组的有效元素（值不为0）个数是 4
4. 原始数组的第4行第5列即 oriArray[4][5]=2
5. 原始数组的第5行第5列即 oriArray[5][5]=1
6. 原始数组的第5行第6列即 oriArray[5][6]=1
7. 原始数组的第6行第5列即 oriArray[6][5]=2

我们用一个数组来存储上面的信息，这个数组就是稀疏数组。那么这个稀疏数组又是多少行多少列的呢？仔细看上面的分析，有两种类型的信息，

1. 原始数组有多少行多少列多少个有效元素
2. 在第几行第几列有一个有效值为 x 的元素

分析这两类信息，可以得出稀疏数组的列应该是3列(原始数组维数+1)，行根据有效数字的个数加1。以此类推，如果三维数组呢？arr[x][y][z] = 1，那么稀疏数组的列就是4列。超过二维的没有验证过。
根据上面的分析即可得到下面这个数组

该数组是一个 (4+1) * 3 的数组，如果只保存这个数组的话，就只需要存储15个元素。将大大的减小存储空间。
当然就如我们上面说的，是在有效数字极少的情况下使用这种方式来存储。如果有效数字很多呢，比如双方总共已经下了100步棋了，就会存在100个有效元素。按照上面推断稀疏数组的方法，将得到一个(100+1) x 3 = 303 个元素的数组，比原始的数组个数还多。这种情况就不适合使用稀疏数组的方式存储了。

二、编码验证

看下面代码

public class Main {

    public static void main(String[] args) {
        //原始数组行
        final int line = 15;
        //原始数组列
        final int col = 15;
        //默认值
        final int defVal = 0;
        //定义原始数组
        int oriArray[][] = new int[line][col];
        //先为原始数组赋初值
        for(int i = 0; i < oriArray.length; i++){
            for(int j = 0; j < oriArray[0].length; j++){
                oriArray[i][j] = defVal;
            }
        }

        oriArray[4][5] = 2;
        oriArray[5][5] = 1;
        oriArray[5][6] = 1;
        oriArray[6][5] = 2;

        //打印原始数组
        System.out.println("====== 打印原始数组 ===========");
        printArray(oriArray);

        //转换为稀疏数组
        int sparseArray[][] = castSparseArray(oriArray,defVal);

        //打印稀疏数组
        System.out.println("====== 打印稀疏数组 ===========");
        printArray(sparseArray);

        //还原为原始数组
        int oriArray2[][] = castOriArray(sparseArray,defVal);

        //打印还原后的原始数组
        System.out.println("====== 打印还原后的原始数组 ===========");
        printArray(oriArray2);
    }

    /**
     * 原始数组转换为稀疏数组
     * @param array
     * @param defVal
     * @return
     */
    public static int[][] castSparseArray(int array[][],int defVal){
        int line = array.length;
        int col = array[0].length;

        //遍历原始数组 获取有效数字个数
        int validCount = 0;
        for(int i = 0;i < line;i++){
            for(int j = 0;j < col;j++){
                //值不等于默认值的就是有效数字
                if(array[i][j] != defVal){
                    validCount++;
                }
            }
        }

        //定义稀疏数组 这里讨论的是二维数组
        int sparseArray[][] = new int[validCount+1][2+1];
        //对稀疏数组第0行赋值
        sparseArray[0][0] = line;
        sparseArray[0][1] = col;
        sparseArray[0][2] = validCount;

        //再遍历原始数组 对稀疏数组赋值
        int count = 1;
        for(int i = 0;i < line;i++){
            for(int j = 0;j < col;j++){
                //值不等于默认值的就是有效数字
                if(array[i][j] != defVal){
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = array[i][j];

                    count++;
                }
            }
        }

        return sparseArray;
    }
	
	/**
     * 稀疏数组还原为原始数组
     * @param array
     * @param defVal
     * @return
     */
    public static int[][] castOriArray(int array[][],int defVal){
        int line = array.length;
        int col = array[0].length;

        //定义原始数组
        int oriArray[][] = new int[array[0][0]][array[0][1]];

        //先为原始数组赋初值
        for(int i = 0; i < oriArray.length; i++){
            for(int j = 0; j < oriArray[0].length; j++){
                oriArray[i][j] = defVal;
            }
        }

        //遍历稀疏数组 为原始数组赋值
        for(int i = 1;i < line;i++){
            oriArray[array[i][0]][array[i][1]] = array[i][2];
        }

        return oriArray;
    }



    private static void printArray(int array[][]){
        int line = array.length;
        int col = array[0].length;
        for(int i = 0; i < line; i++){
            for(int j = 0; j < col; j++){
                System.out.printf("%d\t",array[i][j]);
            }
            System.out.println();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

输出结果

总结：
稀疏数组的目的是为了减小存储的大小。在二维数组中如果存在大量的默认值时，可以将其转换为稀疏数组存储。