稀疏數(shù)組

介紹

當(dāng)我們在處理如五子棋這類棋盤問題時，只有棋盤中的黑子和白字位置對于我們來說是由具體意義的，當(dāng)一個二維數(shù)組中的絕大多數(shù)值都是某一個值時，我們選定位默認(rèn)值，我們可以使用稀疏數(shù)組來保存，以達(dá)到節(jié)約空間的目的

處理過程

1. 創(chuàng)建一個n+1行3列的二維數(shù)組（n為待壓縮數(shù)組中不同于選定默認(rèn)值的個數(shù)）
2. 在第一行分別保存待壓縮數(shù)組的行數(shù)、列數(shù)、n
3. 對每一個不同于默認(rèn)值的值按照行號、列號、值記錄一行

把一個二維數(shù)組壓縮為稀疏數(shù)組

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

把稀疏數(shù)組還原

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