Java プログラミングスキル - データ構造とアルゴリズム「スパース配列」

[[385874]]

基本的な紹介

配列内のほとんどの要素が 0 であるか、同じ値を持つ配列である場合、スパース配列を使用して配列を保存できます。

スパース配列の処理方法は次のとおりです。

配列の行と列の数、および配列に含まれる異なる値の数を記録します。
プログラムのサイズを縮小するために、異なる値を持つ要素の行と列を小さな配列に記録します。

例

元の2次元配列

変換された2次元配列

最初の行は、元の配列の行と列の数、および値の数を記録します（8<<は元の配列の値の数を表します22、15、11、17、-6、39、91、28>>）

変換された2次元配列

2次元配列を疎配列に変換するためのアイデア

元の2次元配列を走査し、有効なデータの数の合計を取得します。
合計に応じて、疎配列sparseArr int(sum+1)(3)を作成できます。
2次元配列の有効なデータをスパース配列に格納する

疎な配列を元の2次元配列に変換するためのアイデア

まず、スパース配列の最初の行を読み取り、最初の行のデータに基づいて元の2次元配列を作成します。
次に、スパース配列の最後の数行のデータを読み取り、元の 2 次元配列に割り当てます。

アプリケーション例

上記と同様の 2 次元配列 (chessboard\map) を保持するには、スパース配列を使用します。
疎配列をディスクに保存し、元の2次元配列を復元します。

コード例

パッケージ com.structures.sparsearray; 
 
パブリッククラスSparseArray { 
 
公共 静的void main(String[] args) {
        // オリジナルの2次元配列11*11を作成する
        //0: チェスの駒がないことを示す、1 は黒いチェスの駒を示す、2 は白いチェスの駒を示す
int [][] chessArr1 = 新しいint [11][11];
        チェスArr1[1][2] = 1;
        チェスArr1[2][3] = 2;
        // 元の2次元配列を出力する
        System.out.println ( "元の2次元配列" );
 ( int [] ints : chessArr1)の場合{
 ( int anInt : ints)の場合{
                System.out.printf ( "%d\t" 、 anInt) ;
            }
            System.out.println( ) ;
        }
        //2次元配列をスパース配列に変換する
        //1. まず 2 次元配列を走査して、ゼロ以外のデータの数を取得します。
整数 合計= 0;
 ( int [] ints : chessArr1)の場合{
 ( int anInt : ints)の場合{
                （整数が0の場合）{
合計++;
                }
            }
        }
        システム.out.println ( "sum = " + sum );
        //2. 対応するスパース配列を作成する
int [][] sparseArr = 新しいint [合計+ 1][3];
        // 疎配列に値を割り当てる
        スパースArr[0][0] = 11;
        スパースArr[0][1] = 11;
        sparseArr[0][2] =合計;
        //元の配列を走査し、スパース配列にゼロ以外の値を格納する
整数  count = 0; // countはゼロ以外のデータの数を記録するために使用されます
( int i = 0; i < chessArr1.length; i++) {
 ( int j = 0 ; j < chessArr1[i].length; j++) {
                チェスArr1[i][j] != 0 の場合 {
カウント++;
                    sparseArr[カウント][0] = i;
                    sparseArr[カウント][1] = j;
                    sparseArr[カウント][2] = chessArr1[i][j];
                }
            }
        }
        // 疎な配列を出力する
        System.out.println( ) ;
        System.out.println ( "得られたスパース配列は~~~~です" );
 ( int [] ints : sparseArr )の場合{
 ( int anInt : ints)の場合{
                （整数が0の場合）{
                    System.out.printf ( "%d\t" 、 anInt) ;
                }
            }
            System.out.println( ) ;
        } 
 
        //スパース配列を元の配列に復元する
int [][] chessArr2 = 新しいint [sparseArr[0][0]][sparseArr[0][1]];
 ( int i = 0; i < sparseArr[0][2]; i++) {
            チェスArr2[sparseArr[i + 1][0]][sparseArr[i + 1][1]] = sparseArr[i + 1][2];
        }
        //復元後の元の配列
        System.out.println ( "復元後の元の配列" );
 ( int [] ints : chessArr2)の場合{
 ( int anInt : ints)の場合{
                System.out.printf ( "%d\t" 、 anInt) ;
            }
            System.out.println( ) ;
        }
    }
 }
 /*
元の2次元配列
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 2 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
合計= 2 
 
結果として得られるスパース配列は~~~~
 11 11 2
 1 2 1
 2 3 2
修復後の元の配列
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 2 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
 */