稀疏數(shù)組可以節(jié)約存儲(chǔ)空間，以圍棋棋盤(pán)舉例萄窜，正常一個(gè)10*10的棋盤(pán)需要用到二維數(shù)組的數(shù)據(jù)結(jié)構(gòu)來(lái)表示 int[10][10] 占用的存儲(chǔ)空間為400個(gè)字節(jié)铃剔，而我們?cè)诖鎯?chǔ)棋盤(pán)數(shù)據(jù)的時(shí)候絕大多數(shù)時(shí)候上面的數(shù)據(jù)都是零值，因此利用稀疏數(shù)組存儲(chǔ)更節(jié)省資源查刻。
下面是這個(gè)稀疏數(shù)組的實(shí)現(xiàn)方式
package com.webxiaohua.algorithm;
import lombok.SneakyThrows;
import java.io.*;
/**
* @Author: shenxinhua
* @Date: 10/14/21 8:57 AM
* @Description: 稀疏數(shù)組 （五子棋）
*/
public class SparseArray {
public static void main(String[] args) {
// 先創(chuàng)建一個(gè)原始的二維數(shù)組 11*11
// 0表示無(wú)棋子 1表示黑子 2表示白子
int chessArr1[][] = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
// 輸出原始的二維數(shù)組
System.out.println("原始的二維數(shù)組：");
for (int[] row : chessArr1) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
// 二維數(shù)組轉(zhuǎn)稀疏數(shù)組
int[][] sparesArr = transform(chessArr1);
// 輸出稀疏數(shù)組
System.out.println("輸出稀疏數(shù)組");
for (int[] row : sparesArr) {
System.out.printf("%d\t%d\t%d", row[0], row[1], row[2]);
System.out.println();
}
// 稀疏數(shù)組存盤(pán)
saveDisk(sparesArr);
System.out.println("存盤(pán)成功：");
// 稀疏數(shù)組讀盤(pán)
int[][] readResult = loadDisk();
System.out.println("讀盤(pán)的稀疏數(shù)組：");
for (int[] row : readResult) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
int[][] chessArr2 = restore(readResult);
System.out.println("還原的二維數(shù)組：");
for (int[] row : chessArr2) {
for (int data : row) {
System.out.printf("%d\t", data);
}
System.out.println();
}
}
// 二維數(shù)組轉(zhuǎn)稀疏數(shù)組
public static int[][] transform(int[][] chessArr) {
// 先遍歷二維數(shù)組得到非0數(shù)據(jù)的個(gè)數(shù)
int sum = 0;
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArr[i][j] > 0) {
sum++;
}
}
}
// 創(chuàng)建對(duì)應(yīng)的稀疏數(shù)組
int sparesArr[][] = new int[sum + 1][3];
// 給稀疏數(shù)組賦值 [[總行键兜，總列，總值],[行穗泵，列普气，值]]
sparesArr[0][0] = 11;
sparesArr[0][1] = 11;
sparesArr[0][2] = sum;
// 遍歷二維數(shù)組，將非0的值存放到稀疏數(shù)組中
int count = 0; //用于記錄是第幾個(gè)非0數(shù)據(jù)
for (int i = 0; i < 11; i++) {
for (int j = 0; j < 11; j++) {
if (chessArr[i][j] > 0) {
count++;
sparesArr[count][0] = i;
sparesArr[count][1] = j;
sparesArr[count][2] = chessArr[i][j];
}
}
}
return sparesArr;
}
// 稀疏數(shù)組轉(zhuǎn)換未二維數(shù)組
public static int[][] restore(int[][] sparesArr) {
// 將稀疏數(shù)組 -> 恢復(fù)成原始的二維數(shù)組
// 先讀取稀疏數(shù)組第一行佃延，根據(jù)第一行的數(shù)據(jù)现诀，創(chuàng)建二維數(shù)組
// 在讀取稀疏數(shù)組后幾行的數(shù)據(jù)，并賦值給原始二維數(shù)組即可
int[][] chessArr2 = new int[sparesArr[0][0]][sparesArr[0][1]];
for (int i = 1; i < sparesArr.length; i++) {
chessArr2[sparesArr[i][0]][sparesArr[i][1]] = sparesArr[i][2];
}
return chessArr2;
}
@SneakyThrows
public static void saveDisk(int[][] data) {
String filePath = "/Users/shenxinhua/workspace/tmp/save.data";
File file = new File(filePath); //存放數(shù)組數(shù)據(jù)的文件
file.createNewFile();
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(data);
oos.close();
}
@SneakyThrows
public static int[][] loadDisk() {
String filePath = "/Users/shenxinhua/workspace/tmp/save.data";
File file = new File(filePath); //存放數(shù)組數(shù)據(jù)的文件
FileInputStream fis = new FileInputStream(file);
ObjectInputStream ois = new ObjectInputStream(fis);
Object o = ois.readObject();
int[][] result = (int[][]) o;
fis.close();
return result;
}
}
