sparsearray詳解

一、什麼是sparsearray

sparsearray（稀疏數組）是一種壓縮存儲數據的方式，它通常用於解決數據中存在大量空值（一般為默認值）的情況。稀疏數組是將二位數組轉換為一維數組來節省存儲空間的一種方法。

如果數組中大部分元素值為0或者同一個值時，我們就可以使用稀疏數組來代替原始的數組，從而節省內存空間。稀疏數組的轉換方法為記錄存儲有值的元素的行列值以及對應的值，最後將這些元素存儲到新的數組中。

// 稀疏數組的創建
int[][] chessArr = new int[11][11];
// 填充原數組
chessArr[1][2] = 1;
chessArr[2][3] = 2;
// 輸出原數組
for (int[] row : chessArr) {
    for (int data : row) {
        System.out.printf("%d\t", data);
    }
    System.out.println();
}

// 將原數組壓縮為稀疏數組
int sum = 0;
for (int i = 0; i < 11; i++) {
    for (int j = 0; j < 11; j++) {
        if (chessArr[i][j] != 0) {
            sum++;
        }
    }
}
int[][] sparseArr = new int[sum + 1][3];
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;
int count = 0;
for (int i = 0; i < 11; i++) {
    for (int j = 0; j < 11; j++) {
        if (chessArr[i][j] != 0) {
            count++;
            sparseArr[count][0] = i;
            sparseArr[count][1] = j;
            sparseArr[count][2] = chessArr[i][j];
        }
    }
}

// 輸出稀疏數組
for (int[] row : sparseArr) {
    for (int data : row) {
        System.out.printf("%d\t", data);
    }
    System.out.println();
}

二、sparsearray的應用場景

sparsearray適用於當數據中某些元素的值非常規律且大量為同一個值時；或者當元素值很大且大部分為0時，可以使用稀疏數組來保存這些數據。下面是一些實際應用場景：

1.棋盤

一張棋盤大部分情況下都是沒有棋子的，而只有少數的點放置了棋子。因此我們可以使用稀疏數組來節省存儲空間。

int[][] chessBoard = new int[11][11];
chessBoard[1][2] = 1;
chessBoard[2][3] = 2;
int[][] sparseArr = toSparseArr(chessBoard);

2、象棋

象棋是一種對稱性較高的棋類，當僅有一方存在棋子時，我們可以使用稀疏數組來保存信息。

int[][] checkerboard = new int[10][9];
checkerboard[0][0] = 1;
int[][] sparseArr = toSparseArr(checkerboard);

3、數組操作記錄

當我們需要對一個數組進行多次操作並記錄每次操作的結果時，可以使用稀疏數組來記錄這些操作。

int[][] arr = new int[3][3];
arr[0][2] = 1;
arr[1][1] = 2;
int[][] sparseArr = toSparseArr(arr);
// 對稀疏數組中的元素進行操作
sparseArr[1][2] = 3;
int[][] arr2 = toArr(sparseArr);
for (int[] row: arr2) {
    for (int data : row) {
        System.out.printf("%d\t", data);
    }
    System.out.println();
}

三、sparsearray的應用示例

下面是一個動態展示將稀疏數組轉換回原始數組的過程：

import java.util.Arrays;

public class SparseArray {

    public static void main(String[] args) {
        // 創建原始二維數組 11 * 11
        // 0: 表示沒有棋子， 1 表示黑子 2 表示藍子
        int[][] chessArr1 = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        // 輸出原始二維數組
        System.out.println("原始二維數組：");
        for (int[] row : chessArr1) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        // 轉換成稀疏數組
        int[][] sparseArr = toSparseArr(chessArr1);
        // 輸出稀疏數組
        System.out.println("稀疏數組：");
        for (int[] row : sparseArr) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        // 轉換回原始二維數組
        int[][] chessArr2 = toArr(sparseArr);
        // 輸出轉換後的二維數組
        System.out.println("轉換後的二維數組：");
        for (int[] row : chessArr2) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }

    /**
     * 將二維數組轉換為稀疏數組
     * @param chessArr 二維數組
     * @return 稀疏數組
     */
    public static int[][] toSparseArr(int[][] chessArr) {
        // 原始數組共有多少個非0值
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr[i][j] != 0) {
                    sum++;
                }
            }
        }
        // 創建稀疏數組
        int[][] sparseArr = new int[sum + 1][3];
        // 為稀疏數組賦值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        // 遍歷原始數組，將非0值存入稀疏數組
        int count = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[i][j];
                }
            }
        }
        return sparseArr;
    }

    /**
     * 將稀疏數組恢復成原始二維數組
     * @param sparseArr 稀疏數組
     * @return 原始二維數組
     */
    public static int[][] toArr(int[][] sparseArr) {
        // 創建原始二維數組
        int[][] 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;
    }
}