Java详解《剑指Offer第二版》面试题4：二维数组中的查找

痛定思痛。 2021-12-01 12:44 296阅读 0赞

> ## 题目描述 ##
> 
> 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

public class Solution {
    
        /*
         1  2  8  9
         2  4  9  12
         4  7  10 13
         6  8  11 15
         寻找6时，我原来的对角线方法就错了。
    
         解法一：用“左下角”的思路来解题：
         1.矩阵是有序的，从左下角来看，向上数字递减，向右数字递增。
         2.因此从左下角开始查找，当要查找数字比左下角数字大时。右移。
         3.要查找数字比左下角数字小时，上移。
    
         解法二：因为每一行是有序的，可以对每一行使用二分查找，这样总的时间复杂度是O(n * log n)
        */
    
        public  boolean Find(int target, int[][] array) {
            if (array == null||array.length==0||array[0].length==0) {
                return false;
            }
    
            int rowNum = array.length; //行数
            int colNum = array[0].length; //列数
    
            /*从左下角开始找*/
            for(int i=rowNum-1,j=0;i>=0 && j<colNum;){
                if(array[i][j]==target){
                    return true;
                }
    
                if (array[i][j]>target){  //左下角 大于 target，说明target可能在左下角的上边
                    i--;
                    continue;
                }
    
                if (array[i][j]<target){  //左下角 小于 target，说明target可能在左下角的左边
                    j++;
                    continue;
                }
    
            }
    
            return false;  //运行至此还没有找到，说明array[][]里面找不到这个target
        }
    
    }