本文共 1604 字，大约阅读时间需要 5 分钟。

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

思路：这是一个二维数组的问题，二维数组题目很少，就这个几个，套路比较简单，理解记住即可。二维数组结构是一个矩阵，爱在思考时从矩阵结构上面进行思考。已知矩阵每一行从左到右递增，每一列从上到下递增，可以得知一个结论：对于任意一个点，它的右边和下边总是比他大（不是右边且下边），他的左上角总是比他小，因此如果对于矩阵中间的某个结点node，如果val>node说明val在node的右边或者下边，如果val<node说明val在node的左下角，这样在每次判断后并没有减少查找范围，因此无法逐步解决问题，因此对于比较的点需要好好选择，这里应该选择左下角或者右上角的点node作为与val比较的点，从右上角开始，如果val<node，那么说明val在node所在列就不用考虑了，这一列一定比node大，因此下一次的搜索范围是array[i][j--];如果val>node,那么说明node的所在行不用考虑了，因为node所在行一定比node小，因此下一次的搜索范围是array[i++][j],以此类推，直到val==node表示找到了，或者i,j越界表示找不到。这里可以使用while循环或者递归来实现。此时时间复杂度是O(m+n)，奥暴力遍历法的时间复杂度是O(mn)

特殊输入：数组为null；数组为空数组，注意空数组int array[][]=new int[0][0];他不为null，只是长度为0，要特殊处理

/*给定一个每行每列排序的二维数组，判断这个数组中是否存在指定的值target，时间复杂度为O(m+n)；这里又发现一个bug,在注释处访问array[i][j]时牛客oj就数组越界异常，提示样例为16，[[]]时报数组越界。但是相同代码在eclipse上和LeetCode的oj上测试都没有问题。在视频题目Sort12：有序矩阵查找练习题上提交也没有问题。*/public class Solution {    public boolean Find(int target, int [][] array) {        //特殊输入        if(array==null) return false;       //求出数组的长度        int rowLength=array.length;        //特殊输入，数组长度为0        if(rowLength==0) return false;        int columnLength=array[0].length;        //定义右上角的点node用于比较val        int i=0;        int j=columnLength-1;        //int node=array[i][j];             --bug        //循环比较或者递归比较        while(i<=rowLength-1&&j>=0){            if(target==array[i][j]) return true;            else if(target>array[i][j]){                i++;             }else{                j--;            }        }        //执行到这里表示没有找到        return false;    }}

转载地址：http://avzin.baihongyu.com/