Javaデータ構造とアルゴリズム分析|疎配列
6931 ワード
GitHubソースの共有
プロジェクトのホームページ:
https://github.com/gozhuyinglong/blog-demos
本明細書のソース:https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures/src/main/java/com/github/gozhuyinglong/datastructures/array
五子棋ゲームのアクセス要件
疎配列を紹介する前に需要を導入し,以下は五子棋の碁盤(15*15)であり,途中まで保存して離れたいので,次回開けても遊び続けたい.どうやって実現しますか?
碁盤の観察から,
2 D配列を用いることで,この要件を解決できることが分かった.しかし、同じ数値の0が多く格納されているという問題も発見されました.これは空間に浪費をもたらしています.別の格納方法はありませんか.答えは疎配列を使用することができます.次に、疎配列がどのように実現されているかを見てみましょう.
Sparse Array
1つの配列のほとんどの要素が0であるか、同じ値である場合、疎配列を使用して配列を保存できます.
疎配列の処理方法は、次のとおりです.レコード配列は全部で数行数列あり、異なる値の数 である.は、異なる値要素を有する行列とその値を小規模な配列に記録し、データの規模を縮小する.
では、上の2次元配列を疎配列ストレージに変えて、どのようなものかを見てみましょう.
第1行(すなわち、0行)は比較的特殊で、rowは総行数を格納し、colは総列数を格納し、valueはゼロ以外の要素の数を格納する.他の行構造は同じで、各行にはゼロ以外の要素情報が格納され、rowは要素が行、colは要素が存在する列、valueは要素の値が格納されます.
コード実装
コードを用いて2次元配列と疎配列の相互変換を実現し,以下は具体的な実装である.
出力結果:
プロジェクトのホームページ:
https://github.com/gozhuyinglong/blog-demos
本明細書のソース:https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures/src/main/java/com/github/gozhuyinglong/datastructures/array
五子棋ゲームのアクセス要件
疎配列を紹介する前に需要を導入し,以下は五子棋の碁盤(15*15)であり,途中まで保存して離れたいので,次回開けても遊び続けたい.どうやって実現しますか?
碁盤の観察から,
int型の2次元配列を用いて記憶することができ,落子のない場所を0,白子記憶1,黒子記憶2とすると,我々の配列は次のようになる可能性がある.2 D配列を用いることで,この要件を解決できることが分かった.しかし、同じ数値の0が多く格納されているという問題も発見されました.これは空間に浪費をもたらしています.別の格納方法はありませんか.答えは疎配列を使用することができます.次に、疎配列がどのように実現されているかを見てみましょう.
Sparse Array
1つの配列のほとんどの要素が0であるか、同じ値である場合、疎配列を使用して配列を保存できます.
疎配列の処理方法は、次のとおりです.
では、上の2次元配列を疎配列ストレージに変えて、どのようなものかを見てみましょう.
第1行(すなわち、0行)は比較的特殊で、rowは総行数を格納し、colは総列数を格納し、valueはゼロ以外の要素の数を格納する.他の行構造は同じで、各行にはゼロ以外の要素情報が格納され、rowは要素が行、colは要素が存在する列、valueは要素の値が格納されます.
コード実装
コードを用いて2次元配列と疎配列の相互変換を実現し,以下は具体的な実装である.
public class SparseArrayDemo {
public static void main(String[] args) {
System.out.println("----------------------- ");
int[][] initialArray = initArray();
printArray(initialArray);
System.out.println("----------------------- --> ");
int[][] sparseArray = arrayConvertSparseArray(initialArray);
printArray(sparseArray);
System.out.println("----------------------- --> ");
int[][] array = sparseArrayConvertArray(sparseArray);
printArray(array);
}
/**
*
*
* @return
*/
static int[][] initArray() {
// 0 ，1 ，2
int[][] array = new int[15][15];
array[3][11] = 1;
array[4][10] = 2;
array[5][9] = 2;
array[6][8] = 2;
array[6][7] = 1;
array[7][8] = 1;
array[7][7] = 2;
array[8][6] = 1;
return array;
}
/**
*
*
* @param array
*/
static void printArray(int[][] array) {
for (int[] row : array) {
for (int data : row) {
System.out.printf("%s\t", data);
}
System.out.println();
}
}
/**
*
*
* @param array
* @return
*/
static int valueCount(int[][] array) {
int count = 0;
for (int[] row : array) {
for (int data : row) {
if (data != 0) {
count++;
}
}
}
return count;
}
/**
*
*
* @param array
* @return
*/
static int[][] arrayConvertSparseArray(int[][] array) {
int rowNum = array.length;
int colNum = array[0].length;
int valueNum = valueCount(array);
int[][] sparseArray = new int[valueNum + 1][3];
sparseArray[0][0] = rowNum;
sparseArray[0][1] = colNum;
sparseArray[0][2] = valueNum;
int rowCount = 1;
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array[i].length; j++) {
int value = array[i][j];
if (value != 0) {
sparseArray[rowCount][0] = i;
sparseArray[rowCount][1] = j;
sparseArray[rowCount][2] = value;
rowCount++;
}
}
}
return sparseArray;
}
/**
*
*
* @param sparseArray
* @return
*/
static int[][] sparseArrayConvertArray(int[][] sparseArray) {
int rowNum = sparseArray[0][0];
int colNum = sparseArray[0][1];
int valueNum = sparseArray[0][2];
int[][] array = new int[rowNum][colNum];
for (int i = 1; i < valueNum + 1; i++) {
int row = sparseArray[i][0];
int col = sparseArray[i][1];
int value = sparseArray[i][2];
array[row][col] = value;
}
return array;
}
}出力結果:
-----------------------
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 1 0 0 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 2 0 0 0 0 0
0 0 0 0 0 0 0 1 2 0 0 0 0 0 0
0 0 0 0 0 0 0 2 1 0 0 0 0 0 0
0 0 0 0 0 0 1 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 0 0 0
----------------------- -->
15 15 8
3 11 1
4 10 2
5 9 2
6 7 1
6 8 2
7 7 2
7 8 1
8 6 1
----------------------- -->
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 1 0 0 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 2 0 0 0 0 0
0 0 0 0 0 0 0 1 2 0 0 0 0 0 0
0 0 0 0 0 0 0 2 1 0 0 0 0 0 0
0 0 0 0 0 0 1 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 0 0 0