稀疏陣列(SparseArray)
當一個二維陣列中大部分元素爲 0 或同一個值的二維陣列時，稀疏陣列可對該二維陣列進行壓縮
儲存。
壓縮儲存的好處
當原陣列中存在大量的無效數據佔用大量的儲存空間時，壓縮儲存可以節省儲存空間，以避
免資源的不必要的浪費 。
處理方法：
記錄原陣列共幾行幾列，有多少個非零值
把每個值的行和列的索引值記錄在一個小規模的陣列中，從而縮小程式規模
二維轉稀疏的思路：
遍歷原始二維陣列，得到非零數值的個數 sum
根據 sum 建立稀疏陣列 sparseArr = new int[sum +1][3]
說明：sum 大小的陣列只能記錄sum條數據，须增添一行來記錄原陣列大小
再次遍歷原始二維陣列，將每個非零數值所對應的行列索引與值，記錄在稀疏陣列中
稀疏轉二維的思路：
讀取稀疏陣列第一行陣列，獲取原陣列的大小，建立新的二維陣列
遍歷稀疏陣列，讀取每行的數據，並將數據恢復到對應的二維陣列中
/* 壓縮前的原始二維陣列
0 1 2 3 4 5 6 7 8 9 <- 行索引
0 0 0 0 0 0 0 0 0 0 0 此時展示的是一個 二維陣列 new Array[7][10]
1 0 0 1 0 0 0 0 0 0 0 該陣列大部分都被同樣的值進行填充
2 0 0 0 0 0 2 0 0 0 0 此時該陣列對浪費了大量的儲存空間
3 0 0 0 8 0 0 0 0 0 0 此等情況下 我們可以使用 稀疏陣列
4 0 0 0 0 0 0 5 0 0 0 進行對該二陣列的壓縮
5 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0
^_ 列索引*/
/* 壓縮後的稀疏陣列
0 1 2 <- 行索引
row col val 該陣列是上述二維陣列的壓縮形式
0 7 10 4 arr[0]中陣列表示：new Array[7][10] 共有 4 個有效數值
1 1 2 1 其中第一個值得位置：在 Array[1][2] 的位置 數值爲 1
2 2 5 2 其中第二個值得位置：在 Array[2][5] 的位置 數值爲 2
3 3 3 8 稀疏陣列用 第一個陣列記錄原陣列的大小和有效值個數
4 4 6 5 後續陣列記錄原陣列有效值的橫縱索引和其值
^_ 列索引*/
程式碼：
package com.DataStructure.sparseArray;
import java.lang.reflect.Array;
public class SparseArray {
public static void main(String[] args) {
SparseArray spar = new SparseArray(); // 建立此類 用以呼叫類中方法
int[][] arr1 = spar.createArray(11, 11); // 獲得一個 縱橫都是 11大小的二維陣列
arr1[1][2] = 1; // 爲陣列增加值
arr1[2][3] = 2;
spar.printArr(arr1); // 列印初始二維陣列
int[][] sparse = spar.getSparse(arr1); // 將初始二維陣列轉換成稀疏陣列
spar.printArr(sparse); // 列印稀疏陣列
int[][] arr2 = spar.parseSparse(sparse); // 將稀疏陣列轉換成二維陣列
spar.printArr(arr2); // 列印轉換出的二維陣列
}
// 建立一個二維陣列並新增預設數據
public int[][] createArray(int row, int col) {
return new int[row][col]; // 傳入參數 返回建立陣列
}
// 將二維陣列解析爲稀疏陣列
public int[][] getSparse(int[][] arr) { // 傳入一個二維陣列
int [][] spsArr = null; // 建立一個稀疏陣列變數
int count = getNotZero(arr); // 得到傳入陣列中非零值的個數用以記錄
int counter = 0; // 用以記錄稀疏陣列已經記錄了第幾個二維陣列有效值
if (arr != null) { // 判空若爲空則不使用 防止報錯
spsArr = new int[count + 1][3]; // 建立稀疏陣列 多一行要記錄二維陣列的大小與有效值個數
spsArr[0][0] = arr.length; // 第一行第一個數據記錄二維陣列的行數
spsArr[0][1] = arr[0].length; // 第一行第二個數據記錄二維陣列的列數
spsArr[0][2] = count; // 第一行第三個數據記錄二維陣列的有效值個數
for (int i = 0; i < arr.length; i++) { // 回圈變數二維陣列的值
for (int j = 0; j < arr[i].length; j++) {
if (arr[i][j] != 0) { // 檢視每個非零的值將其資訊記錄在稀疏陣列中
counter++; // 記錄數據已經寫入第幾行 第幾行數據正好與稀疏陣列下標對應
spsArr[counter][0] = i; // 記錄數值所在原二維陣列行的下標
spsArr[counter][1] = j; // 記錄數值所在原二維陣列列的下標
spsArr[counter][2] = arr[i][j];// 記錄原二維陣列中以上行列下標所對應的值
}
}
}
}
return spsArr; // 若陣列存在返回稀疏陣列，不存在則返回 null
}
// 將稀疏陣列解析爲二維陣列
public int[][] parseSparse(int[][] sparseArr){
int[][] arr = null; // 建立一個二維陣列變數
if (sparseArr != null && 3 == sparseArr[0].length){
// 判空，並且判斷傳入陣列是否爲稀疏陣列
arr = new int[sparseArr[0][0]][sparseArr[0][1]];
// 將稀疏陣列第一行的二維陣列大小值取出恢復二維陣列大小
for (int i = 1; i < sparseArr.length; i++) {
// 將稀疏陣列的每行有效值數據取出，稀疏數據第一行記錄陣列大小 所以從第二行取
arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
// 取出行列對應的索引值，找的陣列對應位置，將原值賦回
}
}
return arr; // 若稀疏陣列存在返回二維陣列，不存在則返回 null
}
// 獲得陣列中非零數據個數
public int getNotZero(int[][] arr) {
int count = -1; // 當傳入陣列爲 null 時，有效數據個數返回 -1
if (arr != null) { // 判空
count = 0; // 當陣列存在但是沒有有效值時候，個數爲0
for (int[] row : arr) { // 遍歷陣列
for (int data : row) {
if (data != 0) { // 判斷陣列中數值是否爲有效值
count++; // 當此次數值有效，個數增長 1
}
}
}
}
return count;
}
// 列印二維陣列
public void printArr(int[][] arr) { // 傳入二維陣列
if (arr != null){ // 判空，若爲空則不呼叫列印 否則報錯
for (int[] row : arr) { // 使用 ForEach 回圈得到二維陣列中的一維陣列
for (int data : row) { // 使用 ForEach 回圈得到一維陣列中的每一個值
System.out.printf("%d\t", data); // 將值列印並在每個值後面增加一個製表符
}
System.out.println(); //每一個數組輸出一行後換行進行輸出下一個陣列
}
} else {
System.out.println("陣列不存在！"); // 若陣列爲空，則輸出陣列不存在
}
}
}
筆記博文，該博文用於私下交流，若有問題請各位大神提點。謝謝！！！