順序付けされた 2 次元配列が与えられ、各行が左から右に増加し、各列が上から下に増加すると仮定します。関数を完成させるには、このような 2 次元配列と整数を入力し、整数かどうかを判断します。はこの 2 次元配列の中にあります。
4×4 の順序付けされた 2 次元配列を想定します。
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
あなたが探している数字は6です。
このアルゴリズムの中心的な考え方は、まず左上隅の数字 9 を取得することです。9 は 6 より大きいため、9 より大きい数字、つまり 4 番目の列を除外して、次に 8 を取得します。 6 より小さい場合は、2 より小さい数値、つまり最初の行を除外できます。同様に、4 を取得して 2 行目を除外し、7 を取得して 2 行目を除外します。 2 番目の列、4 を取得、3 行目を除外、6 を取得、等しい、true を返します。
ここでは再帰を使用して実装します。コードは次のとおりです。
次のようにコードをコピーします。
パブリック クラス FindMatrixNumber {
プライベート静的 FindMatrixNumber インスタンス。
プライベート静的ブール値が見つかりました = false;
public static FindMatrixNumber getInstance() {
if (インスタンス == null) {
インスタンス = 新しい FindMatrixNumber();
}
インスタンスを返します。
}
public static boolean find(int 行列[][], int 数値) {
if (行列 == null || 行列.length == 0 || 行列[0].length == 0) {
false を返します。
} それ以外 {
System.out.println("****検索開始****");
findMatrixNumber(行列, 行列.長さ, 0, 行列[0].長さ,
番号）;
System.out.println("****検索終了*****");
}
見つかったものを返します。
}
private static void findMatrixNumber(int 行列[][], int rows, int row,
int 列、int 数値) {
if (行 > 行 - 1)
戻る;
int コーナー番号 = マトリックス[行][列 - 1];
System.out.println(cornerNumber);
if (コーナー番号 == 数値) {
見つかった = true;
戻る;
} else if (cornerNumber < 数値) {
findMatrixNumber(行列, 行, ++行, 列, 数値);
} else if (コーナー番号 > 番号) {
findMatrixNumber(行列, 行, 行, --columns, 数値);
}
}
}
テストコードは次のとおりです。
次のようにコードをコピーします。
パブリック クラス TestFindMatrixNumber {
public static void main(String[] args) {
int 行列[][] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
System.out.println(FindMatrixNumber.find(matrix, 6));
}
}
テストコードを実行した結果は次のようになります。
次のようにコードをコピーします。
****探し始めます****
9
8
2
4
7
4
6
*****検索終了*****
真実