剣指offer 1-2 D配列での検索
剣指offer 1-2 D配列での検索
1、テーマの説明
1つの2次元配列(各1次元配列の長さは同じ)では、各行が左から右に増加する順序でソートされ、各列が上から下に増加する順序でソートされます.関数を完了し、このような2次元配列と整数を入力して、配列に整数が含まれているかどうかを判断します.
2、構想分析
この2 D配列には、上から下へ、左から右へと増加する特性があります.法則をまとめると,行列の右上または左下からクエリすべきであることが分かった.各回に1行または列を削除し、検索範囲を縮小できます.
右上隅を例にとると、まず右上隅の数字を選択し、その数字が検索する数字に等しい場合、検索プロセスは終了します.検索する数値より大きい場合は、カラムの他の要素が検索する数値より大きいことを示し、カラムを削除できます.検索する数字より小さい場合は、その行の他の要素も検索する数字より小さいことを示し、その行を削除できます.これにより、比較のたびに1行または1列を除去し、さらに検索範囲を縮小することができ、時間的複雑度はO(n)である.
3、コード
1、テーマの説明
1つの2次元配列(各1次元配列の長さは同じ)では、各行が左から右に増加する順序でソートされ、各列が上から下に増加する順序でソートされます.関数を完了し、このような2次元配列と整数を入力して、配列に整数が含まれているかどうかを判断します.
2、構想分析
この2 D配列には、上から下へ、左から右へと増加する特性があります.法則をまとめると,行列の右上または左下からクエリすべきであることが分かった.各回に1行または列を削除し、検索範囲を縮小できます.
右上隅を例にとると、まず右上隅の数字を選択し、その数字が検索する数字に等しい場合、検索プロセスは終了します.検索する数値より大きい場合は、カラムの他の要素が検索する数値より大きいことを示し、カラムを削除できます.検索する数字より小さい場合は、その行の他の要素も検索する数字より小さいことを示し、その行を削除できます.これにより、比較のたびに1行または1列を除去し、さらに検索範囲を縮小することができ、時間的複雑度はO(n)である.
3、コード
package com.jianzhioffer;
public class offer_01 {
public static boolean find(int[][] matrix,int number) {
//
if(matrix==null || matrix.length<1 || matrix[0].length<1 ) {
return false;
}
//
int rows=matrix.length;
int cols=matrix[0].length;
//
int row=0;
int col=cols-1;
//
while(row>=0 && row<rows && col>=0 && col<cols) {
//
if(matrix[row][col]==number) {
return true;
} else if(matrix[row][col]>number) {
// ,
col--;
} else {
row++;
}
}
return false;
}
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 8, 9},
{2, 4, 9, 12},
{4, 7, 10, 13},
{6, 8, 11, 15}
};
System.out.println(find(matrix, 7)); //
System.out.println(find(matrix, 5)); //
System.out.println(find(matrix, 1)); //
System.out.println(find(matrix, 15)); //
System.out.println(find(matrix, 0)); //
System.out.println(find(matrix, 16)); //
System.out.println(find(null, 16)); // ,
}
}