1.定義

稀疏數組可以看做是普通二位數組的壓縮，但是這裡說的

*當一個數組中大部分元素為０，或者為同一個值的數組時，可以使用稀疏數組來保存該數組如圖

2.好處

* 原數組中存在大量的無效數據，佔據了大量的存儲空間，真正有用的數據卻少之又少

*把具有不同值的元素的行列及值記錄在一個小規模的數組中，從而縮小程序的規模

* 壓縮存儲可以節省存儲空間以避免資源的不必要的浪費，在數據序列化到磁盤時，壓縮存儲可以提高IO效率

3.稀疏數組的結構

*記錄數組一共有幾行幾列，有多少個不同的值

* 第一行存儲原始數據總行數，總列數，總的非0數據個數

* 接下來每一行都存儲非0數所在行，所在列，和具體值(如下圖)

行列都是11的二位數組

把上面的二維數組轉化為稀疏數組

備註：因為數組的下標是從0開始的，所以他們的標號也是從0開始的(重要)

4.二維數組 轉 稀疏數組的思路

*遍歷原始的二維數組，得到有效數據的個數 sum

*根據sum 就可以創建 稀疏數組 sparseArr int[sum + 1] [3]

*將二維數組的有效數據數據存入到 稀疏數組

5.稀疏數組轉原始的二維數組的思路

*先讀取稀疏數組的第一行，根據第一行的數據，創建原始的二維數組，

比如上面的 chessArr2 = int [11][11]

*在讀取稀疏數組後幾行的數據，並賦給 原始的二維數組 即可.

6.代碼實現

<code>public class Sparsearray {

\tpublic static void main( String[] args) {
\t\tSystem.out.println("===========二維數組轉換稀疏數組============");
\t\tint[][] array=new int[11][11];
\t\tarray[1][2]=1;
\t\tarray[2][3]=2;
\t\tSystem.out.println("============轉換前的二維數組============");
\t\tforToarray(array);
\t\tSystem.out.println("============轉換後的二維數組============");
\t\tint[][] sparsearry = arrayToSparsearry(array);
\t\tforToarray(sparsearry);
\t\tSystem.out.println("===========將稀疏數組轉化為原始數組============");
\t\tarray = sparsearryToArray(sparsearry);
\t\tforToarray(array);
\t\t
\t}
\t/**
\t *二維數組轉換稀疏數組
\t * @param array 

\t */
\tprivate static int [][] arrayToSparsearry(int[][] array) {
\t\tint sum=1;
\t\tfor (int i = 0; i < array.length; i++) {
\t\t\tint[] datas=array[i];
\t\t\tfor (int j = 0; j < datas.length; j++) {
\t\t\t\tif (array[i][j]!=0) {
\t\t\t\t\tsum++;
\t\t\t\t}
\t\t\t}
\t\t}
\t\t
\t\tint [][] sparse=new int[sum][3];
\t\tint s=0;
\t\tsparse[s][0]=array.length;
\t\tsparse[s][1]=array[0].length;
\t\tsparse[s][2]=sum-1;
\t\tfor (int i = 0; i < array.length; i++) {
\t\t\tint[] datas=array[i];
\t\t\tfor (int j = 0; j < datas.length; j++) {
\t\t\t\tint a=array[i][j];
\t\t\t\tif (a!=0) {
\t\t\t\t\ts++;
\t\t\t\t\tsparse[s][0]=i;
\t\t\t\t\tsparse[s][1]=j;
\t\t\t\t\tsparse[s][2]=a;
\t\t\t\t}
\t\t\t}
\t\t}

\t\treturn sparse;
\t}
\t/**
\t *遍歷數組
\t * @param array
\t */
\tprivate static void forToarray(int[][] array) {
\t\tfor (int i = 0; i < array.length; i++) {
\t\t\tint [] ints=array[i];
\t\t\tfor (int j = 0; j < ints.length; j++) {
\t\t\t\tSystem.out.print("  "+array[i][j]);
\t\t\t}
\t\t\tSystem.out.println("");
\t\t}
\t}
\t /*
\t  * 稀疏數組轉化為原始數組
\t * @param array
\t */ 

\tprivate static int [][] sparsearryToArray(int[][] array) {
\t\tint [] [] arrays=new int [array[0][0]][array[0][1]];
\t\t    for (int i = 1; i < array.length; i++) {
\t\t\t\tint[] js = array[i];
\t\t\t\tfor (int j = 0; j < js.length; j++) {
\t\t\t\t\tarrays[array[i][0]][array[i][1]]=array[i][2];
\t\t\t\t}
\t\t\t\t
\t\t\t}
\t\treturn arrays;
\t}
}/<code>

*執行後的結果如下

<code>===========二維數組轉換稀疏數組============
============轉換前的二維數組============
  0  0  0  0  0  0  0  0  0  0  0
  0  0  1  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  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  0  0  0  0  0  0  0  0  0
============轉換後的二維數組============
  11  11  2
  1  2  1
  2  3  2
===========將稀疏數組轉化為原始數組============
  0  0  0  0  0  0  0  0  0  0  0
  0  0  1  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  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  0  0  0  0  0  0  0  0  0/<code> 

閱讀更多 高鐵愛好者 的文章

關鍵字: 算法 數據量 數據結構