Javaで元の配列をスパース配列に変換する方法

1. それは何ですか?

たとえば、11 * 11 のバックギャモン ボードがあり、プログラムを使用してそれをシミュレートしたい場合、それは 2 次元配列でなければなりません。次に、黒石を表すのに 1 を使用し、白石を表すのに 2 を使用します。チェス盤上に黒石と白石が 1 つずつしかない場合、この 2 次元配列には 1 と 2 が 1 つだけあり、残りは無意味です。チェスの駒を表さない 0 は次のようになります。

0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 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 であるか、同じ値を持つ場合、スパース配列を使用して配列を保存できます。なぜこれを行うのでしょうか?スペースを節約できるからです。

2. 使い方は？

• 元の配列の行数と列数、および異なる値の数を記録します

• 行と列を配置します。異なる値と値を持つ要素の列が小規模配列に記録され、この小規模配列はスパース配列

3 と呼ばれます。

#現在の状況は次のとおりです。 元の 6 * 7 の配列:

0   0   0   22   0   0   15
0   11  0   0    0   17   0
0   0   0  -6    0   0    0
0   0   0   0    0   39   0
91  0   0   0    0   0    0
0   0   28  0    0   0    0

まず、疎配列の最初の行と最初の列に、要素配列が何行あるかを記録します。最初の行と 2 番目の列は、元の配列が何列であるかを記録します。最初の行と最初の列は、元の配列に異なる値がいくつあるか (0 を除く) を記録します。したがって、スパース配列の 1 行は次のようになります。

行    列    值
6     7     8

スパース配列の 2 行目から開始して、各行には、元の配列内の 0 以外の値の行、列、および値のサイズが記録されます。たとえば、2 行目に元の配列の行、列、および値 22 を記録する場合、スパース配列の 2 行目は次のようになります。

行    列    值
0     3     22

次に、このメソッドを使用して 15、11 を記録します。 、17、-6、39、91、28 の関連情報が含まれるため、元の配列から最終的に変換されたスパース配列は次のようになります。

行    列    值
6     7     8
0     3     22
0     6     15
1     1     11
1     5     17
2     3     -6
3     5     39
4     0     91
5     2     28

これにより、6 * 7 配列が 9 * 3 配列に変換され、圧縮が実現されます。効果 。

4. 元の配列とスパース配列を変換するためのアイデア:

元の配列をスパース配列に変換する:

• 2 つをトラバースします。次元 配列は有効な配列の数を取得します。 count;

• count に基づいてスパース配列を作成できます。

  int[count 1][3];

• 有効な配列をスパース配列に保存します

スパース配列を変換します元の配列へ:

• 疎配列の最初の行を読み取ります。配列の最初の行に基づいて、元の配列の行数と列数を知ることができ、元の配列;

• スパース配列の後の数行の配列を読み取り、それを元の配列に代入します

5。練習:

public class SparseArray {
    public static void main(String[] args){
        // 创建一个 11 * 11的原始数组
        int[][] arr1 = new int[11][11];
        arr1[1][2] = 1;
        arr1[2][3] = 2;

        // 原始数组转稀疏数组
        // 1. 遍历，得到非0数据的个数以及所在的行列
        int count = 0;
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr1[i].length; j++) {
                if (arr1[i][j] != 0){
                    count ++;
                    map.put(i+ "," + j, arr1[i][j]);
                }
            }
        }
        // 2. 创建稀疏数组
        int[][] sparseArr = new int[count + 1][3];
        sparseArr[0][0] = arr1.length;
        sparseArr[0][1] = arr1[0].length;
        sparseArr[0][2] = count;
        // 3. 给稀疏数组赋值
        int row = 1;
        for (String key : map.keySet()){
            String[] ij = key.split(",");
            int i = Integer.parseInt(ij[0]);
            int j = Integer.parseInt(ij[1]);
            sparseArr[row][0] = i;
            sparseArr[row][1] = j;
            sparseArr[row][2] = map.get(key);
            row ++;
        }
        // 4. 遍历稀疏数组
        for (int i = 0; i < sparseArr.length; i++) {
            for (int j = 0; j < sparseArr[i].length; j++) {
                System.out.print(sparseArr[i][j] + "   ");
            }
            System.out.println("\r\n");
        }

        // 稀疏数组恢复原始数组
        // 1. 根据第一行第一列第二列创建出原始数组
        int i = sparseArr[0][0];
        int j = sparseArr[0][1];
        int[][] arr2 = new int[i][j];
        // 2. 给原始数组赋值
        for (int k = 1; k < sparseArr.length; k++) {
            int x = sparseArr[k][0];
            int y = sparseArr[k][1];
            int val = sparseArr[k][2];
            arr2[x][y] = val;
        }
        // 3. 遍历转换的数组
        for (int a = 0; a < arr2.length; a++) {
            for (int b = 0; b < arr2[a].length; b++) {
                System.out.print(arr2[a][b] + "   ");
            }
            System.out.println("\r\n");
        }
    }
}

上記のコードは、元の配列と疎な配列の間の相互変換を実現します. 疎な配列を柔軟に使用することで、実行メモリを節約し、プログラムのパフォーマンスを向上させることができます。

以上がJavaで元の配列をスパース配列に変換する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。