『數據結構與演算法』稀疏數組

• 2021 年 2 月 14 日
• 筆記
• 數據結構, 數據結構與演算法, 數組, 稀疏數組, 演算法

微信搜索：碼農StayUp
主頁地址：//gozhuyinglong.github.io
源碼分享：//github.com/gozhuyinglong/blog-demos

五子棋遊戲的存取需求

在介紹稀疏數組前我們先來引入一個需求，下面是一個五子棋的棋盤（15 * 15），玩到中途時想要保存離開，希望下次打開還可以繼續玩。我們怎麼實現呢？

從對棋盤的觀察來看，我們可以使用int型的二維數組進行存儲，將未落子的地方存儲0，白子存儲1，黑子存儲2，那麼我們的數組可能是這樣的：

可以看出，使用二維數組是能解決這個需求的。但我們也發現了一個問題，上面存儲相同數值的0比較多，這對空間造成了浪費，有沒有另外一種存儲方式呢？答案是可以使用稀疏數組，下面我們來看稀疏數組是怎麼實現的！

稀疏數組（Sparse Array）

當一個數組中大部分元素是0，或者是一個相同的值時，可以使用稀疏數組來保存該數組。

稀疏數組的處理方式是：

1. 記錄數組一共有幾行幾列，以及不同值的數量
2. 把具有不同值元素的行列及其值記錄在一個小規模的數組中，從而縮小數據的規模。

那我們把上面二維數組轉為稀疏數組存儲，看是什麼樣子的。

第一行（即：0行）比較特殊，row存儲總行數，col存儲總列數，value存儲非零（不同值）元素的數量；
其他行結構相同，每一行存儲一條非零元素資訊，row存儲元素所在行，col存儲元素所在列，value存儲元素的值。

程式碼實現

我們使用程式碼來實現二維數組與稀疏數組的相互轉換，下面是具體的實現！

public class SparseArrayDemo {

    public static void main(String[] args) {
        System.out.println("-----------------------普通數組");
        int[][] initialArray = initArray();
        printArray(initialArray);
        System.out.println("-----------------------普通數組 --> 稀疏數組");
        int[][] sparseArray = arrayConvertSparseArray(initialArray);
        printArray(sparseArray);
        System.out.println("-----------------------稀疏數組 --> 普通數組");
        int[][] array = sparseArrayConvertArray(sparseArray);
        printArray(array);
    }

    /**
     * 初始化五子棋數組
     *
     * @return
     */
    static int[][] initArray() {
        // 0為空，1為白子，2為黑子
        int[][] array = new int[15][15];
        array[3][11] = 1;
        array[4][10] = 2;
        array[5][9] = 2;
        array[6][8] = 2;
        array[6][7] = 1;
        array[7][8] = 1;
        array[7][7] = 2;
        array[8][6] = 1;
        return array;
    }

    /**
     * 列印二維數組
     *
     * @param array
     */
    static void printArray(int[][] array) {
        for (int[] row : array) {
            for (int data : row) {
                System.out.printf("%s\t", data);
            }
            System.out.println();
        }
    }

    /**
     * 統計非零值數量
     *
     * @param array
     * @return
     */
    static int valueCount(int[][] array) {
        int count = 0;
        for (int[] row : array) {
            for (int data : row) {
                if (data != 0) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 普通數組轉為稀疏數組
     *
     * @param array
     * @return
     */
    static int[][] arrayConvertSparseArray(int[][] array) {
        int rowNum = array.length;
        int colNum = array[0].length;
        int valueNum = valueCount(array);

        int[][] sparseArray = new int[valueNum + 1][3];
        sparseArray[0][0] = rowNum;
        sparseArray[0][1] = colNum;
        sparseArray[0][2] = valueNum;

        int rowCount = 1;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                int value = array[i][j];
                if (value != 0) {
                    sparseArray[rowCount][0] = i;
                    sparseArray[rowCount][1] = j;
                    sparseArray[rowCount][2] = value;
                    rowCount++;
                }
            }
        }
        return sparseArray;
    }

    /**
     * 稀疏數組轉為普通數組
     *
     * @param sparseArray
     * @return
     */
    static int[][] sparseArrayConvertArray(int[][] sparseArray) {
        int rowNum = sparseArray[0][0];
        int colNum = sparseArray[0][1];
        int valueNum = sparseArray[0][2];

        int[][] array = new int[rowNum][colNum];

        for (int i = 1; i < valueNum + 1; i++) {
            int row = sparseArray[i][0];
            int col = sparseArray[i][1];
            int value = sparseArray[i][2];
            array[row][col] = value;
        }

        return array;
    }
}

輸出結果：

-----------------------普通數組
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	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	2	0	0	0	0	0	
0	0	0	0	0	0	0	1	2	0	0	0	0	0	0	
0	0	0	0	0	0	0	2	1	0	0	0	0	0	0	
0	0	0	0	0	0	1	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	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	
-----------------------普通數組 --> 稀疏數組
15	15	8	
3	11	1	
4	10	2	
5	9	2	
6	7	1	
6	8	2	
7	7	2	
7	8	1	
8	6	1	
-----------------------稀疏數組 --> 普通數組
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	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	2	0	0	0	0	0	
0	0	0	0	0	0	0	1	2	0	0	0	0	0	0	
0	0	0	0	0	0	0	2	1	0	0	0	0	0	0	
0	0	0	0	0	0	1	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	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	

推薦閱讀

• 《 數組 》
• 《 稀疏數組 》
• 《 鏈表（單鏈表、雙鏈表、環形鏈表） 》
• 《 棧 》
• 《 隊列 》
• 《 樹 》
• 《 二叉樹 》
• 《 二叉查找樹（BST） 》
• 《 AVL樹（平衡二叉樹） 》
• 《 B樹 》
• 《 散列表（哈希表） 》

作者：碼農StayUp
出處：//mp.weixin.qq.com/s/YYemaomm10HiKs9MoKHKIw
版權：本文採用「署名-非商業性使用-相同方式共享 4.0 國際 (CC BY-NC-SA 4.0)」知識共享許可協議進行許可。