稀疏數組
- 2021 年 12 月 17 日
- 筆記
在遇到棋盤或者地圖等問題時，常常需要構造一個二維數組。以棋盤為例，需要大量的0（或者其他相同的默認數值）來組成棋盤的基本結構，而數組中非0值的位置卻很少。為了節省空間，可以用稀疏數組來存儲相應資訊。
稀疏數組是一個3列的二維數組，稀疏數組的第一行總是存儲原來二維數組的行列和有效值的資訊。分別是：
- 第一行第一列存原來二維數組的總行數
- 第一行第二列存原來二維數組的總列數
- 第一行第三列存原來二維數組的非0（有效）值的總個數
從稀疏數組的第二行往下，存放原來二維數組的有效資訊，每一個有效值的資訊在稀疏數組中的存放形式如下：
- 第1列存放某一個有效值出現的行
- 第2列存放那一個有效值出現的列
- 第3列存放那個有效的值
原來一個9*9的大數組，在使用稀疏數組後，變成一個5*3的小數組，節約了空間。圖上能反應出稀疏數組與原來二維數組的對應關係。
-
二維數組–>稀疏數組
通過遍歷原來的二維數組可以找到每一個有效值的資訊，然後賦值給稀疏數組。
java程式碼實現：
1 public static int[][] twoToSparse(int[][] arr) { 2 //將二維數組變成稀疏數組 3 int sum = 0; //記錄原數組有幾個非0的值，用於確定稀疏數組的行數 4 int columnNum = 0; //記錄原數組的列數 5 for (int[] ints : arr) { 6 columnNum = ints.length; //獲取列數 7 for (int anInt : ints) { 8 if (anInt != 0) { 9 sum++; 10 } 11 } 12 } 13 int[][] sparseArr = new int[sum + 1][3]; 14 sparseArr[0][0] = arr.length; 15 sparseArr[0][1] = columnNum; 16 sparseArr[0][2] = sum; 17 int count = 0;//紀錄出現的值是第幾個 18 for (int i = 0; i < arr.length; i++) { //遍歷原來的二維數組，找到非0處的值，將資訊賦值給稀疏數組 19 for (int j = 0; j < columnNum; j++) { 20 if (arr[i][j] != 0) { 21 count++; //第幾個出現就放在第幾行（第0行存放原數組的 總行數，總列數，總非0的值的數量） 22 sparseArr[count][0] = i; //第一列存放行數 23 sparseArr[count][1] = j; //第二列存放列數 24 sparseArr[count][2] = arr[i][j]; //第三列存放具體的值 25 } 26 } 27 } 28 return sparseArr; 29 }
-
稀疏數組–>二維數組
通過遍歷稀疏數組的資訊，很快就能獲得二維數組的資訊，然後將原來需要的二維數組恢復。
java程式碼實現：
1 public static int[][] sparseToTwo(int[][] sparseArr) { 2 //將稀疏數組恢復成二維數組 3 int[][] arr = new int[sparseArr[0][0]][sparseArr[0][1]]; //利用稀疏數組中第一行的總行列數資訊，創建一個二維數組 4 if (sparseArr[0][2] == 0) { 5 return arr; //沒有有效值，直接返回只有默認值的數組，這裡默認值是0，不需要進行另外的賦值操作 6 } else { 7 for (int i = 1; i < sparseArr.length; i++) { 8 arr[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2]; //遍歷稀疏數組，讀取行，列，值資訊，賦給二維數組 9 10 } 11 return arr; 12 } 13 }
