Java實作稀疏數組轉化

文章目錄

• 稀疏數組
• 普通數組壓縮為稀疏數組
• 将稀疏數組還原為普通數組

稀疏數組

• 什麼是稀疏數組？

  稀疏數組可以看做是普通數組的壓縮，但是這裡說的普通數組是值無效資料量遠大于有效資料量的數組

普通數組壓縮為稀疏數組

代碼實作

public class SparseArray {
    public static void main(String[] args) {
        int[][] array = new int[4][5];
        //初始化二維數組
        array[0][2] = 1;
        array[1][1] = 2;
        array[2][3] = 3;

        //記錄普通數組中的有效值個數并且周遊普通數組
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j <array[i].length ; j++) {
                if (array[i][j] != 0) {
                    //本例将不為0的數視為有效值
                    count++;
                }
                System.out.print(array[i][j]+" ");
            }
            System.out.println();
        }


        //建立稀疏數組
        int[][] sparesArray = new int[count+1][3];
        sparesArray[0][0] = array.length;
        sparesArray[0][1] = array[0].length;
        sparesArray[0][2] = count;
        int index = 0;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                if (array[i][j] != 0){
                	//将普通數組轉化為稀疏數組
                    index++;
                    sparesArray[index][0] = i;
                    sparesArray[index][1] = j;
                    sparesArray[index][2] = array[i][j];
                }
            }
        }

        //周遊稀疏數組
        for (int i = 0; i < sparesArray.length; i++) {
            for (int j = 0; j < sparesArray[i].length; j++) {
                System.out.print(sparesArray[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
    }
}
           

輸出結果

将稀疏數組還原為普通數組

代碼實作

//還原稀疏數組
        int[][] revertArray = new int[sparesArray[0][0]][sparesArray[0][1]];
        for (int i = 1; i < sparesArray.length; i++) {
            int row = sparesArray[i][0];
            int colunm = sparesArray[i][1];
            revertArray[row][colunm] = sparesArray[i][2];
        }

        System.out.println("還原後的普通數組");
        //周遊還原後的稀疏數組
        for (int i = 0; i < revertArray.length; i++) {
            for (int j = 0; j < revertArray[i].length; j++) {
                System.out.print(revertArray[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }
           

輸出結果