目錄

1.稀疏數(shù)組

2.稀疏數(shù)組的使用

2.1 二維數(shù)組轉(zhuǎn)換為稀疏數(shù)組

2.2 稀疏數(shù)組轉(zhuǎn)換為二維數(shù)組

---

1.稀疏數(shù)組

稀疏數(shù)組（Sparse Array）：當一個數(shù)組中的大部分元素為相同的值，可使用稀疏數(shù)組來保存該數(shù)組，可以將稀疏數(shù)組看做是普通數(shù)組的壓縮

例如

?數(shù)組arr中許多值為0，若對二維數(shù)組直接進行存儲，則會存儲許多相同的數(shù)值0，造成空間的浪費，此時，我們可以用稀疏數(shù)組對其進行存儲

2.稀疏數(shù)組的使用

要對二維數(shù)組進行存儲，我們需要知道二維數(shù)組的行和列、不同數(shù)值的數(shù)量以及不同元素的位置和值

稀疏數(shù)組的第一行，存放二維數(shù)組arr的行數(shù)、列數(shù)、不同數(shù)值的數(shù)量sum

?后面幾行，存放不同值元素在二維數(shù)組arr中的行、列、數(shù)值

代碼實現(xiàn)

創(chuàng)建二維數(shù)組

 int[][] arr = new int[6][5];arr[1][0] = 1;arr[1][3] = 6;arr[4][3] = 2;

2.1 二維數(shù)組轉(zhuǎn)換為稀疏數(shù)組

（1）遍歷二維數(shù)組，確定不同元素的個數(shù)sum

        int sum = 0;for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr[0].length; j++) {if(arr[i][j] != 0){sum++;}}}

（2）根據(jù)sum創(chuàng)建稀疏數(shù)組

int[][] sparseArr = new int[sum+1][3];

(3) 遍歷二維數(shù)組，對稀疏數(shù)組進行賦值

//稀疏數(shù)組的第一行分別存放二維數(shù)組的行數(shù)、列數(shù)以及不同元素的個數(shù)sparseArr[0][0] = arr.length;sparseArr[0][1] = arr[0].length;sparseArr[0][2] = sum;//再對不同元素進行存儲int k = 0;for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr[0].length; j++) {if(arr[i][j] != 0){k++;//分別存放不同元素的行、列以及數(shù)值sparseArr[k][0] = i;sparseArr[k][1] = j;sparseArr[k][2] = arr[i][j];}}}

2.2 稀疏數(shù)組轉(zhuǎn)換為二維數(shù)組

（1）創(chuàng)建二維數(shù)組

int[][] arr1 = new int[sparseArr[0][0]][sparseArr[0][1]];

（2）遍歷稀疏數(shù)組， 對不同值元素進行賦值

        //遍歷稀疏數(shù)組，對不同值元素進行賦值for (int i = 1; i < sparseArr.length; i++) {arr1[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];}

?

完整代碼

public class Test {public static void main(String[] args) {//創(chuàng)建二維數(shù)組int[][] arr = new int[6][5];arr[1][0] = 1;arr[1][3] = 6;arr[4][3] = 2;System.out.println("****二維數(shù)組****");for (int[] row: arr) {for (int data: row) {System.out.printf("%d ",data);}System.out.println();}int sum = 0;for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr[0].length; j++) {if(arr[i][j] != 0){sum++;}}}//創(chuàng)建稀疏數(shù)組int[][] sparseArr = new int[sum+1][3];//稀疏數(shù)組的第一行分別存放二維數(shù)組的行數(shù)、列數(shù)以及不同元素的個數(shù)sparseArr[0][0] = arr.length;sparseArr[0][1] = arr[0].length;sparseArr[0][2] = sum;//再對不同元素進行存儲int k = 0;for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr[0].length; j++) {if(arr[i][j] != 0){k++;//分別存放不同元素的行、列以及數(shù)值sparseArr[k][0] = i;sparseArr[k][1] = j;sparseArr[k][2] = arr[i][j];}}}System.out.println("****稀疏數(shù)組****");for (int[] row: sparseArr) {for (int data: row) {System.out.printf("%d ",data);}System.out.println();}//創(chuàng)建二維數(shù)組int[][] arr1 = new int[sparseArr[0][0]][sparseArr[0][1]];//遍歷稀疏數(shù)組，對不同值元素進行賦值for (int i = 1; i < sparseArr.length; i++) {arr1[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];}System.out.println("****二維數(shù)組****");for (int[] row: arr1) {for (int data: row) {System.out.printf("%d ",data);}System.out.println();}}
}

運行結(jié)果