稀疏陣列 Sparse Array

基本介紹

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

處理方法

第一列記錄陣列 一共有幾列幾行，有多少個不同 的值
把具有不同值的元素的行列及值記錄在一個小規模的陣列中，從而 縮小程序 的規模

Screen_Shot_2022-01-12_at_17.02.54.png

應用場景

使用稀疏數組，來保留類似前面的二維數組(棋盤、地圖等等)
把稀疏數組存盤，並且可以從新恢復原來的二維數組數

二維陣列轉稀疏陣列的思路

遍歷原始的二維陣列，得到有效數據的個數 sum (第一列的val)
根據 sum 就可以創建稀疏陣列 sparseArr int[sum + 1] [3]
將二維陣列的有效數據存入到稀疏陣列

稀疏陣列轉原始的二維陣列的思路

先讀取稀疏陣列的第一行，根據第一行的數據，創建原始的二維陣列，比如上面的chessArr2 = int[11][11]
在讀取稀疏陣列後幾行的數據，並賦給原始的二維陣列即可

稀疏陣列實現（程式碼）

package com.xiran.sparse_array;

public class Main {

    public static void main(String[] args) {
        // 創建一個原始的二維陣列 11 * 11
        // 0: 代表沒有棋子 1: 代表黑子 2: 代表藍子
        int[][] chessArr = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        chessArr[4][5] = 2;

        System.out.println("原始二維陣列：");
        for (int[] row : chessArr) {
            for (var data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

/*
    原始二維陣列：
    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    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
*/

        // 將二維陣列轉爲稀疏陣列的思路
        // 1. 先歷遍二維陣列 得到非0數字的個數
        int sum = 0;
        for (int[] row : chessArr) {
            for (int data : row) {
                if (data != 0) sum++;
            }
        }
        System.out.println("有效數值個數(非0)：" + sum);

/*
    有效數值個數(非0)：3
*/

        // 創建對應稀疏陣列
        int[][] sparseArr = new int[sum + 1][3];
        // 給稀疏陣列賦值 row col val
        sparseArr[0][0] = chessArr.length;
        sparseArr[0][1] = chessArr[0].length;
        sparseArr[0][2] = sum;

        // 二維陣列的有效數據存入到稀疏陣列
        int count = 0; // 用於記錄第幾個(列)非0
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[i].length; j++) {
                if (chessArr[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[i][j];
                }
            }
        }

        System.out.println("\n處理後稀疏陣列：");
        System.out.println("\trow\tcol\tval");
        for (var i = 0; i < sparseArr.length; i++) {
            System.out.printf("%d)\t%d\t%d\t%d\n", i, sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
        }

/*
    處理後稀疏陣列：
            row    col    val
    0)    11  11    3
    1)    1      2      1
    2)    2      3      2
    3)    4      5      2
*/
        /*
                 * 從稀疏陣列還原到二維陣列
         * 1. 先讀取稀疏陣列的第一行，根據第一行的數據，創建原始的二維陣列，比如上面的chessArr2 = int[11][11]
         * 2. 在讀取稀疏陣列後幾行的數據，並賦給原始的二維陣列即可
         */

        // 1. 先讀取稀疏陣列的第一行，根據第一行的數據，創建原始的二維陣列
        int sparseRow = sparseArr[0][0];
        int sparseCol = sparseArr[0][1];
        int[][] chessArr2 = new int[sparseRow][sparseCol];

        // 輸出恢復後的二維陣列
        System.out.println("\n還原爲二維陣列(未填入有效資料)：");
        for (int[] row : chessArr2) {
            for (var data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

        // 2. 在讀取稀疏陣列後幾行的數據，並賦給原始的二維陣列即可
        for (int i = 1; i < sparseArr.length; i++) {
            int row = sparseArr[i][0];
            int col = sparseArr[i][1];
            int val = sparseArr[i][2];
            chessArr2[row][col] = val;
        }
        // 輸出恢復後的二維陣列
        System.out.println("\n還原爲二維陣列：");
        for (int[] row : chessArr2) {
            for (var data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }
}