定义

  • 稀疏数组是经过特殊处理后的二维数组。
  • 当一个二维数组中存在大量相同值的时候，可以考虑转换为稀疏数组来进行存储，从而达到节省内存空间的目的。
  • 二维数组中存在的大量相同值我们称之为无效值，除开无效值，剩下的就是有效值。
1
2
3
4
5
6
7
8
9
10
11
12
13

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                                             10 10 2
0 0 0 5 0 0 0 0 0 0                 ======>                     1  2  2
0 0 0 0 0 0 0 0 0 0                                             4  3  5
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 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. 稀疏数组第一行固定用于存储原数组信息，例如，我们存储的是一个3行4列，有1个有效值的数组，第一行就是3 4 1

  2. 稀疏数组一定是一个n行3列的二维数组

    • 因为我们有多个有效值，每一个有效值，我们都需要用一行来进行存储，所以有n行
    • 3列分别对应了有效值的行、列、值

代码实现

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
// 创建一个10*10的二维数组，在数组存入两个有效值
int[][] array1 = new int[10][10];
array1[1][2] = 2;
array1[4][3] = 5;

//我们打印一下，在控制台会看到如下一个二维数组
/*
        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 5 0 0 0 0 0 0 
        0 0 0 0 0 0 0 0 0 0 
        0 0 0 0 0 0 0 0 0 0 
        0 0 0 0 0 0 0 0 0 0 
        0 0 0 0 0 0 0 0 0 0 
        0 0 0 0 0 0 0 0 0 0
*/
for (int i = 0;i<array1.length;i++){
    for (int j = 0;j<array1[i].length;j++){
        System.out.print(array1[i][j] + " ");
        if (j == array1[i].length-1) {
            System.out.println();
        }
    }
}

// 获取数组中有效值的个数
// 因为当前数组中初始值全部为0，所以这里不为0的就是我们的有效值，把它们筛选出来
int sum = 0;
for(int i = 0;i < array1.length; i++){
    for(int j = 0;j < array1[i].length; j++){
        if(array1[i][j] != 0){
            sum++;
        }
    }
}

// 创建一个稀疏数组
// 稀疏数组的第一行存放的是原数组的信息，所以稀疏数组的行数=有效值+1，列数3固定
int[][] array2 = new int[sum+1][3];

//用稀疏数组第一行，存放原数组的信息：行/列/有效值个数
array2[0][0] = array1.length;
array2[0][1] = array1[0].length;
array2[0][2] = sum;

// 再次遍历二维数组，将有效值存入稀疏数组中
// count++的使用恰好让我们在存储有效值时跳过了第一行
int count = 0;
for(int i = 0;i < array1.length; i++){
    for(int j = 0;j < array1[i].length; j++){
        if(array1[i][j] != 0){
            count++;
            array2[count][0] = i;
            array2[count][1] = j;
            array2[count][2] = array1[i][j];
        }
    }
}

// 控制台打印查看一下我们转换完成的稀疏数组
/*
        10 10 2 
        1 2 2 
        4 3 5 
*/
for (int i = 0;i<array2.length;i++){
    for (int j = 0;j<array2[i].length;j++){
        System.out.print(array2[i][j] + " ");
        if (j == array2[i].length-1) {
            System.out.println();
        }
    }
}

//恢复
//1. 用稀疏数组中第一行信息创建二维数组
int[][] array3 = new int[array2[0][0]][array2[0][1]];
//2. 填充二维数组
for(int i = 1;i < array2.length;i++){
    array3[array2[i][0]][array2[i][1]] = array2[i][2];
}