剑指Offer面试题：1.二维数组中的查找

一、题目：二维数组中的查找
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。
————————————————
图片说明
二、解题思路
首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。
　　例如，我们要在上述的二维数组中查找数字7的步骤如下图所示：
————————————————
图片说明
三、解决问题

package swordoffer;
/*
 二维数组中的查找
 题目：
 在一个二维数组中，每一行都按照从左到右递增的顺序排序，
 每一列都按照从上到下递增的顺序排序。
 请完成一个函数，输入这样的一个二维数组和一个整数，
 判断数组中是否含有该整数。
 */
public class Solution01 {
    public static void main(String[] args) {
        System.out.println("hello");
        Solution01 sword = new Solution01();
        sword.test1();
        sword.test2();
        sword.test3();
    }
    /*
    要求时间复杂度 O(M + N)，空间复杂度 O(1)。
    其中 M 为行数，N 为 列数。
    规模：
    利用二维数组由上到下，由左到右递增的规律，
    那么选取右上角或者左下角的元素array[row][col]与target进行比较，
    当target小于元素array[row][col]时，那么target必定在元素a所在行的左边,
    即col--；
    当target大于元素array[row][col]时，那么target必定在元素a所在列的下边,
    即row++；
     */
    public boolean Find(int target, int [][] array) {
        if(null == array || 0 == array.length || 0 == array[0].length){
            return false;
        }
        int rows = array.length;// 行数M
        int cols = array[0].length;// 列数N
        int row = 0,col = cols - 1;//重置行、列号
        while(row <= rows - 1 && col >= 0){
            if(target == array[row][col]){
                //若 target 等于 查找的数字：则查找成功
                return true;
            }else if(target > array[row][col]){
                //若 target 大于 查找的数字：则行数++,即代表下一次只需要在其下方区域查找
                row++;
            }else{
                //若 target 小于 查找的数字：则列数--,即代表下一次只需要在其左边区域查找
                col-- ;
            }
        }
        //若 查找后，没有查到,返回false
        return false;
    }
    //测试用例
    //1.要查找的数字在数组中
    public void test1() {
        System.out.print("test1：");
        int[][] matrix = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } };
        System.out.println(Find(7,matrix));
    }
    //2.要查找的数字不在数组中
    public void test2(){
        System.out.print("test2：");
        int[][] matrix = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } };
        System.out.println(Find(5,matrix));
    }
    //3.数组为空
    public void test3() {
        System.out.print("test3：");
        int[][] matrix = null;
        System.out.println(Find(5,matrix));
    }
}

努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。
图片说明