实际问题
如上图11*11的棋盘，现在需要做存盘和复盘的功能，如何处理？
分析问题
首先想到的使用二维数组表示棋子所在位置及自身值，但是如上图所示有很多默认值，如果这样记录会有许多没有意义的数据。
处理思路
- 记录数组共有几行几列，有多少个不同值
- 把不同值记录在一个小规模的数组中
- 稀疏数组的第一行记录原始数组的行数、列数、有效元素个数；从稀疏数组的第二行开始记录有效元素的所在行、所在列以及值。
编程实现
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
|
package com.eh.ftd.dsa.ds;
/**
* 稀疏数组
* 棋盘 有白子和黑子，使用稀疏数组来优化存盘并提供功能予以复盘
*
* @author David Li
* @create 2020/06/11 16:39
*/
public class SparseArr {
/**
* 打印棋盘,1 表示白子;2表示黑子
*
* @param chessBoard
*/
public static void printChessBoard(int[][] chessBoard) {
if (chessBoard.length < 2) {
throw new RuntimeException("输入有误");
}
// 获取棋盘行数
int rowNumber = chessBoard.length;
// 获取棋盘列数
int colNumber = chessBoard[0].length;
// 遍历棋盘并打印 1表示白子;2表示黑子
for (int row = 0; row < rowNumber; row++) {
for (int col = 0; col < colNumber; col++) {
System.out.printf(chessBoard[row][col] + " ");
}
// 换行
System.out.println();
}
}
/**
* 将原始棋盘转换成稀疏数组
*
* @param chessBoard
* @return
*/
public static int[][] convert2SparseArr(int[][] chessBoard) {
if (chessBoard.length < 2) {
throw new RuntimeException("输入有误");
}
// 获取棋盘行数
int rowNumber = chessBoard.length;
// 获取棋盘列数
int colNumber = chessBoard[0].length;
// 活跃棋格数目
int activeNumber = 0;
// 遍历棋盘获取活跃棋格数
for (int row = 0; row < rowNumber; row++) {
for (int col = 0; col < colNumber; col++) {
if (chessBoard[row][col] > 0) {
activeNumber++;
}
}
}
// 组装稀疏数组
// 第一行
int[][] sparseArr = new int[activeNumber + 1][3];
sparseArr[0][0] = rowNumber;
sparseArr[0][1] = colNumber;
sparseArr[0][2] = activeNumber;
// 剩下行
int temp = 1;
for (int row = 0; row < rowNumber; row++) {
for (int col = 0; col < colNumber; col++) {
if (chessBoard[row][col] > 0) {
sparseArr[temp][0] = row;
sparseArr[temp][1] = col;
sparseArr[temp][2] = chessBoard[row][col];
temp++;
}
}
}
return sparseArr;
}
/**
* 将稀疏数组转换成原始数组, 模拟复盘操作
*
* @param sparseArr
* @return
*/
public static int[][] convert2OriginalChessBoard(int[][] sparseArr) {
// 获取行列数和活跃棋格数
int rowNumber = sparseArr[0][0];
int colNumber = sparseArr[0][1];
int activeNumber = sparseArr[0][2];
// 遍历稀疏数组 将值设置到原始数组
int[][] originChessBoard = new int[rowNumber][colNumber];
for (int i = 1; i <= activeNumber; i++) {
// 稀疏数组的行列值分别对应原始数组的行列值
originChessBoard[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
}
return originChessBoard;
}
public static void main(String[] args) {
// 构造原始棋盘 0-空格 1-白子 2-黑子
int[][] chessBoard = new int[11][11];
chessBoard[1][2] = 2;
chessBoard[2][1] = 1;
chessBoard[3][3] = 2;
System.out.println("=======原始棋盘==========");
printChessBoard(chessBoard);
// 转换成稀疏数组
int[][] sparseArr = convert2SparseArr(chessBoard);
System.out.println("=======转换后的稀疏数组==========");
printChessBoard(sparseArr);
// 转换成原始数组，模拟复盘
int[][] originChessBoard = convert2OriginalChessBoard(sparseArr);
System.out.println("=======稀疏数组复盘后的原始棋盘==========");
printChessBoard(originChessBoard);
}
}
|
运行结果：
扩展
- 稀疏数组主要应用于压缩数据
- 如果是三维数组比如空间数据，同样可以使用稀疏数组(xnum,ynum,znum,activeNum)(x,y,z,val)来表示。
如上图11*11的棋盘，现在需要做存盘和复盘的功能，如何处理？
