JAVA描述算法和資料結構(01)：稀疏數組和二維數組轉換

本文源碼：GitHub·點這裡 || GitEE·點這裡

一、基本簡介

1、基礎概念

在矩陣中，若數值為0的元素數目遠遠多于非0元素的數目，并且非0元素分布沒有規律時，則稱該矩陣為稀疏矩陣；與之相反，若非0元素數目占大多數時，則稱該矩陣為稠密矩陣。定義非零元素的總數比上矩陣所有元素的總數為矩陣的稠密度。

2、處理方式

1)、記錄數組一共有幾行幾列，有多少個不同的值
2)、把具有不同值的元素的行列及值記錄在稀疏數組中，可以縮小程式代碼的複雜度。
           

3、圖解描述

稀疏數組表示
[0] 3 4 4 二維數組，3行，4列，4個非0的值；
[1] 1 2 2 一行，2列的值是2；
[2] 1 3 3 一行，3列的值是3；
…以此類推
           

4、五子棋場景

使用稀疏數組描述
行    列    值
[0]  11    11    2
[1]  1     2     1
[2]  2     3     2
           

二、代碼實作

1、轉換流程

二維數組轉稀疏數組

1)、周遊二維數組，得到非零元素的個數
2)、建立稀疏數組
3)、二維數組的非零元素寫入稀疏數組
           

稀疏數組轉二維數組

1)、讀取稀疏數組的首行，建立二維數組
2)、根據稀疏數組描述的有效元素，給二維數組指派
           

2、代碼實作

1)、核心流程

1、棋盤：基于二維數組
2、二維數組轉稀疏數組
3、稀疏數組轉二維數組
           

2)、方法一：生成二維數組

public static int[][] printChess (){
    // 二維數組表示 11 * 11 的棋盤，0表示沒有棋,1表示 黑, 2 表示藍
    int chessArray[][] = new int[11][11];
    chessArray[1][2] = 1;
    chessArray[2][3] = 2;
    for (int[] row : chessArray) {
        for (int data : row) {
            System.out.printf("%d\t", data);
        }
        System.out.println();
    }
    return chessArray ;
}
           

3)、方法二：轉為稀疏數組

public static int[][] convertTwoArray (int chessArray[][]){
    // 有效元素：先周遊二維數組 得到非0資料的個數
    int unZeroSum = 0;
    for (int i = 0; i < 11; i++) {
        for (int j = 0; j < 11; j++) {
            if (chessArray[i][j] != 0) {
                unZeroSum++;
            }
        }
    }
    // 行：有效元素+1，列：3列
    int sparseArray[][] = new int[unZeroSum+1][3] ;
    sparseArray[0][0] = 11 ;// 0行0列值：11
    sparseArray[0][1] = 11 ;// 0行1列值：11
    sparseArray[0][2] = unZeroSum ;// 0行2列值：unZeroSum
    // 周遊二維數組，将非0的值存放到稀疏數組中
    // unZeroCount 用于記錄是第幾個非0資料,也就是稀疏數組的行
    int unZeroCount = 0; //
    for (int i = 0; i < 11; i++) {
        for (int j = 0; j < 11; j++) {
            if (chessArray[i][j] != 0) {
                unZeroCount++;
                sparseArray[unZeroCount][0] = i;
                sparseArray[unZeroCount][1] = j;
                sparseArray[unZeroCount][2] = chessArray[i][j];
            }
        }
    }
    // 輸出稀疏數組的形式
    for (int i = 0; i < sparseArray.length; i++) {
        System.out.printf("%d\t%d\t%d\t\n",
                sparseArray[i][0],
                sparseArray[i][1],
                sparseArray[i][2]);
    }
    return sparseArray ;
}
           

4)、方法三：轉為二維數組

public static void convertSparseArray (int sparseArray[][]){
    // 讀取稀疏數組首行建立二維數組==>> int chessArray[][] = new int[11][11];
    int chessArray[][] = new int[sparseArray[0][0]][sparseArray[0][1]] ;
    // 非零元素指派給二維數組
    for(int i = 1; i < sparseArray.length; i++) {
        // 幾行、幾列、是什麼值
        chessArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
    }
    // 列印二維數組
    for (int[] row : chessArray) {
        for (int data : row) {
            System.out.printf("%d\t", data);
        }
        System.out.println();
    }
}
           

5)、主程式調用

public static void main(String[] args) {
    // 棋盤：基于二維數組
    int chessArray[][] = printChess () ;
    System.out.println("==========================");
    // 二維數組轉稀疏數組
    int sparseArray[][] = convertTwoArray(chessArray) ;
    System.out.println("==========================");
    // 稀疏數組轉二維數組
    convertSparseArray(sparseArray);
}
           

三、源代碼位址

GitHub·位址
https://github.com/cicadasmile/model-arithmetic-parent
GitEE·位址
https://gitee.com/cicadasmile/model-arithmetic-parent