談一下稀疏陣列-有解無憂

對于一個初窺資料結構的人來說，稀疏陣列確實可以很好的幫助你鍛煉思維，

但自從第三次科技革命后，人們都一直在做著用空間去換取時間的損事，而以時間換空間的稀疏陣列，倒也跟北大考古專業有些心心相惜，

稀疏陣列的基本介紹：

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

如何創建一個稀疏陣列：

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

（小規模陣列便是稀疏陣列）

應用場景：

像在撰寫的五子棋程式中，有存盤退出和續上局功能在存盤的時候，將黑白子以及空位都分別以1,2,0存放在一個二維陣列中，當棋盤上空位比較多的時候，大量的0（重復資料）會占用較高的空間，為了節省空間，便有了稀疏陣列，

如上圖，將一個棋盤映射成為一個二維陣列，在陣列中，有大量重復的資料. 這時，我們可以將棋盤的行、列以及非0的資料抽取出來，分別作為稀疏陣列的 SparseArray[0][0]、SparseArray[0][1]、SparseArray[0][2]，將非重復資料的行、列、值依次存盤在稀疏陣列中，便有了一個較小規模的陣列，以節省空間，

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

遍歷原始的二維陣列，得到有效的資料個數sum；
根據個數創建稀疏陣列sparseArr int[sum + 1][3];
將二維陣列的有效資料存入到稀疏陣列，

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

先讀取稀疏陣列的第一行，根據第一行創建原始陣列chessArr2 = int[11]；
在讀取稀疏陣列后幾行的資料，并賦給原始的二維陣列，

package com.perwrj.sparsearray;

public class SparseArray {

    public static void main(String[] args) {
        /*
         * 原始陣列的創建與遍歷
         */
        System.out.println("原始的二維陣列");
        int  chessArr [][] = new int[11][11];
        chessArr [1][2] = 1;
        chessArr [2][3] = 2;
        for (int[] is : chessArr) {
            for (int is2 : is) {
                System.out.print("\t" + is2);
            }
            System.out.println("\n");
        }
        
        /*
         * 將原始陣列轉換為稀疏陣列
         */
//        獲取原始陣列中不為零值的個數
        int sum = 0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[i].length; 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 < 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("稀疏陣列");
        for (int[] is : sparseArr) {
            for (int is2 : is) {
                System.out.print("\t" + is2);
            }
            System.out.println("\n");
        }
        
        /*
         * 稀疏陣列轉換為原始陣列
         */
//        用稀疏陣列第一行創建原始陣列
        int chessArr2 [][] = new int[sparseArr[0][0]][sparseArr[0][1]];
        
//        遍歷賦值原始陣列
        for (int i = 1; i < sparseArr.length; i++) {
                chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        
//        遍歷還原后的陣列
        System.out.println("還原后的二維陣列");
        for (int[] is : chessArr2) {
            for (int is2 : is) {
                System.out.print("\t" + is2);
            }
            System.out.println("\n");
        }
    }

}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262834.html

標籤：其他

上一篇：[書目20210224]陸蓉行為金融學講義

下一篇：Kubernetes和docker----1.開始使用k8s和docker