一、稀疏數組

稀疏數組

基本介紹

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

如下圖所示：

稀疏數組的處理方法：

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

稀疏數組轉換思路

二維數組轉稀疏數組思路：

1. 遍歷原始的二維數組，得到有效數據的個數sum
2. 根據sum可以創建稀疏數組sparseArr[sum+1] [3]
3. 將二維數組的有效數據存入到稀疏數組

稀疏數組轉二維數組思路：

1. 先讀取稀疏數組的第一行，根據第一行的數據，創建原始的二維數組
2. 再讀取稀疏數組後幾行的數據，並賦值給原始的二維數據即可

代碼實現

二維數組 轉 稀疏數組

public class SparseArray {
    public static void main(String[] args) {
        //創建一個二維數組 11*11
        int arr[][] = new int[11][11];
        arr[1][2] = 1;
        arr[3][4] = 2;
        //先將原始數組列印出來
        System.out.println("原始二維數組為：");
        for (int[] row : arr) {
            for (int data : row) {
                System.out.print(data + "  ");
            }
            System.out.println();
        }

        /**
         * 將二維數組 轉 稀疏數組
         */
        //1、先遍歷二維數組得到非0數據的個數
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (arr[i][j] != 0) {
                    sum++;
                }
            }
        }
        //2、創建對應的稀疏數組
        int[][] sparseArr = new int[sum + 1][3];
        //3、給稀疏數組第一行賦值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        //4、遍歷二維數組，將非0的值存放到sparseArr中
        int count = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (arr[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = arr[i][j];
                }
            }
        }

        //列印稀疏數組
        System.out.println();
        System.out.println("得到的稀疏數組為：");
        for (int[] row : sparseArr) {
            for (int data : row) {
                System.out.print(data + "     ");
            }
            System.out.println();
        }
    }
}

稀疏數組 轉 二維數組

接著上面的稀疏數組，將其轉回二維數組，下麵提供一個轉化方法:

public int[][] SparseArrayToArray(int[][] sparseArr) {
    //1、先根據稀疏數組的第一行，根據第一行的數據，創建原始的二維數組
    int arr[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
    //2、再讀取稀疏數組的後幾行數據（從第二行開始），並賦值給原始的二維數組即可
    for (int i = 1; i < sparseArr.length; i++) {
        arr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
    }
    return arr;
}