剑指offer(3) 二维数组中的查找

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

/*
 * -------------------------------------------------------------------------------
 * Copyright © 2014-2021 China Mobile (SuZhou) Software Technology Co.,Ltd.
 *
 * The programs can not be copied and/or distributed without the express
 * permission of China Mobile (SuZhou) Software Technology Co.,Ltd.
 *
 * @description:
 *
 * @author: liuqiang@cmss.chinamobile.com
 * 2021/03/01 20:38
 *
 * -------------------------------------------------------------------------------
 */
public class Solution03 {

    public static void main(String[] args) {
        System.out.println("hello");
        Solution03 sword = new Solution03();
        sword.test1();
        sword.test2();
        sword.test3();
    }
    /*
        要求时间复杂度 O(M + N)，空间复杂度 O(1)。
        其中 M 为行数，N 为 列数。
        规模：
        利用二维数组由上到下，由左到右递增的规律，
        那么选取右上角或者左下角的元素array[row][col]与target进行比较，
        当元素array[row][col]大于target时，那么target必定在元素a所在行的左边,
        即col--；
        当t元素array[row][col]小于arget时，那么target必定在元素a所在列的下边,
        即row++；
         */
    public boolean Find(int target, int [][] array) {
        // array.length表示的是行数,array[0].length表示的是列数
        if (null == array || 0 == array.length || array[0].length == 0) {
            return false;
        }
        int rows = array.length; //行数
        int cols = array[0].length; //列数
        int row = 0, col  = cols - 1; // 需要移动的行列游标
        while (row <= rows - 1 && col >= 0) {
            if (array[row][col] == target) {
                // 若选取数组中的数字等于target，则查找成功
                return true;
            }else if (array[row][col] > target) {
                // 若选取数组中的数字 > target；则列数--,即代表下一次只需要在选取数字左边区域查找
                col--;
            }else {
                // 若选取数组中的数字 < target；则行数++,即代表下一次只需要在其下方区域查找
                row++;
            }
        }
        // 若查找后，没有查到，返回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));
    }

}

日子很滚烫，又暖又明亮。向阳而生