剣指offer 1-2 D配列での検索

11684 ワード

剣指offer 1-2 D配列での検索
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));     //      ,     
        
    }
}