个人博客

稀疏数组

2021/5/1

# 稀疏数组

# 定义

稀疏数组可以看做是普通数组的压缩，但是这里说的普通数组是指无效数据量远大于有效数据量的数组。

# 使用场景

稀疏数组有很多的使用场景，比如五子棋（思路：单数为黑棋，双数为白棋；数字从小到大可记录下棋顺序），棋盘很大，但是一盘下完后，大部分的位置都是没有棋字的。这是可以使用稀疏数组存储，使用时也可以还原成初始的二维数组。

# 举例

image-20210527091550740

例如如下数组，即可使用稀疏数组压缩：

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
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
1
2
3
4
5
6
7
8
9
10
11

压缩后的结果：

11 11 2
1  2  1
2  4  2
1
2
3

原本占用了11 * 11空间，压缩后只占用了3 * 3的空间。

# 为什么要进行数组的压缩存储？

  • 原数组中存在大量的无效数据，占据了大量的存储空间，真正有用的数据却少之又少
  • 压缩存储可以节省存储空间以避免资源的不必要的浪费，在数据序列化到磁盘时，压缩存储可以提高IO效率

# 处理方法

  1. 记录数组一共有几行几列，有多少个不同的值
  2. 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序规模

如下：

0  0  0  22 0  0  15
0  11 0  0  0  17 0
0  0  0  -6 0  0  0
0  0  0  0  0  39 0
91 0  0  0  0  0  0
0  0  28 0  0  0  0
1
2
3
4
5
6
行（row） 列（col） 值（value）
[0] 6 7 8
[1] 0 3 22
[2] 0 6 15
[3] 1 1 11
[4] 1 5 17
[5] 2 3 -6
[6] 3 5 39
[7] 4 0 91
[8] 5 2 28

# 稀疏数组存储方式

  1. 第一行存储原始数据总行数，总列数，总的非0数据个数
  2. 接下来每一行都存储非0数所在行，所在列，和具体值 例如上面的稀疏数组： 第一行代表：原始的二维数组一共6行7列，并且有8个非0值 第二行代表：原始的二维数组的第1行第4列的值为22 ........................

# 稀疏数组与二维数组互相转换

# 思路

二维数组转稀疏数组思路:

  1. 遍历原始的二维数组，得到有效数据的个数sum

  2. 根据sum就可以创建稀疏数组sparseArr[sum+1][3]

  3. 将二维数组的有效数据数据存入到稀疏数组

稀疏数组转二维数组思路:

  1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组。

  2. 在读取稀疏数组后几行的数据，并赋给原始的二维数组即可。

# 代码实现

import org.junit.Test;
/**
 * description:稀疏数组
 *
 * @author RenShiWei
 * Date: 2021/5/24 16:51
 **/
public class SparseArray {
    /**
     * description:二维数组转稀疏数组
     *
     * @param originalArr 原始的二维数组
     * @return 稀疏数组
     * @author RenShiWei
     * Date: 2021/5/27 9:46
     */
    public int[][] arrayToSparse(int[][] originalArr) {
        //遍历原始二维数组得到有效数据的个数（方便创建稀疏数组）
        int sum = 0;
        for (int[] arr : originalArr) {
            for (int data : arr) {
                if (data != 0) {
                    sum++;
                }
            }
        }
        int[][] sparseArray = new int[sum + 1][3];
        sparseArray[0][0] = originalArr.length;
        sparseArray[0][1] = originalArr[0].length;
        sparseArray[0][2] = sum;
        //记录第几个有效数据
        int count = 0;
        for (int i = 0; i < originalArr.length; i++) {
            for (int j = 0; j < originalArr[0].length; j++) {
                //不为0的数据，记录在稀疏数组
                if (originalArr[i][j] != 0) {
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = originalArr[i][j];
                }
            }
        }
        return sparseArray;
    }
    /**
     * description:稀疏数组转二维数组
     *
     * @param sparseArray 稀疏数组
     * @return 原始的二维数组
     * @author RenShiWei
     * Date: 2021/5/27 9:46
     */
    public int[][] sparseToArray(int[][] sparseArray) {
        int[][] originalArr = new int[sparseArray[0][0]][sparseArray[0][1]];
        for (int i = 1; i < sparseArray.length; i++) {
            //稀疏数组第二行开始的数据，恢复到二维数组
            originalArr[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }
        return originalArr;
    }
    /**
     * description:格式化数组输出
     *
     * @param arr 待输出的数组
     * @author RenShiWei
     * Date: 2021/5/27 9:58
     */
    public void arrayToString(int[][] arr) {
        for (int[] row : arr) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
    /**
     * description:测试用例1
     *
     * @author RenShiWei
     * Date: 2021/5/27 10:04
     */
    @Test
    public void test() {
        int[][] arr = new int[][] {
                {0, 0, 0, 22, 0, 0, 15},
                {0, 11, 0, 0, 0, 17, 0},
                {0, 0, 0, - 6, 0, 0, 0},
                {0, 0, 0, 0, 0, 39, 0},
                {91, 0, 0, 0, 0, 0, 0},
                {0, 0, 28, 0, 0, 0, 0}
        };
        System.out.println("---二维数组转稀疏数组---");
        int[][] sparseArray = arrayToSparse(arr);
        arrayToString(sparseArray);
        System.out.println("---稀疏数组转二维数组---");
        int[][] originalArr = sparseToArray(sparseArray);
        arrayToString(originalArr);
    }
    /**
     * description:测试用例2
     *
     * @author RenShiWei
     * Date: 2021/5/27 10:04
     */
    @Test
    public void test2() {
        int[][] arr = new int[][] {
                {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},
                {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},
        };
        System.out.println("棋盘测试");
        System.out.println("---二维数组转稀疏数组---");
        int[][] sparseArray = arrayToSparse(arr);
        arrayToString(sparseArray);
        System.out.println("---稀疏数组转二维数组---");
        int[][] originalArr = sparseToArray(sparseArray);
        arrayToString(originalArr);
    }
}
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