稀疏數組 介紹 當我們在處理如五子棋這類棋盤問題時，只有棋盤中的黑子和白字位置對於我們來說是由具體意義的，當一個二維數組中的絕大多數值都是某一個值時，我們選定位預設值，我們可以使用稀疏數組來保存，以達到節約空間的目的 處理過程 1. 創建一個n+1行3列的二維數組（n為待壓縮數組中不同於選定預設值的 ...
稀疏數組
介紹
當我們在處理如五子棋這類棋盤問題時，只有棋盤中的黑子和白字位置對於我們來說是由具體意義的，當一個二維數組中的絕大多數值都是某一個值時，我們選定位預設值，我們可以使用稀疏數組來保存，以達到節約空間的目的
處理過程
- 創建一個n+1行3列的二維數組（n為待壓縮數組中不同於選定預設值的個數）
- 在第一行分別保存待壓縮數組的行數、列數、n
- 對每一個不同於預設值的值按照行號、列號、值記錄一行
把一個二維數組壓縮為稀疏數組
public class SparseArray {
public int[][] array2SparseArray(int[][] res){
int n=0;
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[i].length;j++) {
if(res[i][j]!=0) {
n++;
}
}
}
int[][] tar=new int[n+1][3];
tar[0][0]=res.length;
tar[0][1]=res[0].length;
tar[0][2]=n;
int row=1;
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[i].length;j++) {
if(res[i][j]!=0) {
tar[row][0]=i;
tar[row][1]=j;
tar[row][2]=res[i][j];
row++;
}
}
}
return tar;
}
public static void main(String[] args) {
int[][] res=new int[4][5];
res[1][2]=1;
res[0][3]=2;
res[2][0]=1;
res[2][2]=1;
SparseArray sa=new SparseArray();
sa.print(res);
int[][] tar = sa.array2SparseArray(res);
sa.print(tar);
}
public void print(int[][] res) {
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[i].length;j++) {
System.out.print(res[i][j]+" ");
}
System.out.println();
}
}
}
輸出：
0 0 0 2 0
0 0 1 0 0
1 0 1 0 0
0 0 0 0 0
4 5 4
0 3 2
1 2 1
2 0 1
2 2 1
把稀疏數組還原
public class SparseArray {
public int[][] array2SparseArray(int[][] res){
int n=0;
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[i].length;j++) {
if(res[i][j]!=0) {
n++;
}
}
}
int[][] tar=new int[n+1][3];
tar[0][0]=res.length;
tar[0][1]=res[0].length;
tar[0][2]=n;
int row=1;
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[i].length;j++) {
if(res[i][j]!=0) {
tar[row][0]=i;
tar[row][1]=j;
tar[row][2]=res[i][j];
row++;
}
}
}
return tar;
}
public int[][] sparseArray2Array(int[][] res){
int rows=res[0][0];
int cols=res[0][1];
int n=res[0][2];
int[][] tar=new int[rows][cols];
for(int i=1;i<=n;i++) {
int row=res[i][0];
int col=res[i][1];
int val=res[i][2];
tar[row][col]=val;
}
return tar;
}
public static void main(String[] args) {
int[][] res=new int[4][5];
res[1][2]=1;
res[0][3]=2;
res[2][0]=1;
res[2][2]=1;
SparseArray sa=new SparseArray();
sa.print(res);
int[][] tar = sa.array2SparseArray(res);
sa.print(tar);
int[][] res2 = sa.sparseArray2Array(tar);
sa.print(res2);
}
public void print(int[][] res) {
for(int i=0;i<res.length;i++) {
for(int j=0;j<res[i].length;j++) {
System.out.print(res[i][j]+" ");
}
System.out.println();
}
}
}
輸出：
0 0 0 2 0
0 0 1 0 0
1 0 1 0 0
0 0 0 0 0
4 5 4
0 3 2
1 2 1
2 0 1
2 2 1
0 0 0 2 0
0 0 1 0 0
1 0 1 0 0
0 0 0 0 0
