题解 | #二维数组中的查找#

两个重要点

• 1.每一行都按照从左到右递增的顺序排序
• 2.每一列都按照从上到下递增的顺序排序
• 那么起始点a选择右上角*
• 1.如果a下方位置b小于等于target，由于b>=a,很明显a所在这行就直接淘汰了
• 2.如果b位置大于target了，说明这一列就淘汰了，再往下走都是大于target的,该往左走找新列了
• 3.拢共m行n列，每次必定淘汰一行或者淘汰一列，时间复杂度O(m+n)

    //判断数组中是否含有该整数target
    public boolean Find(int target, int [][] array) {
        if(array==null||array.length==0||array[0].length==0) return false;
        //1.能向下就向下，不能向下就向左        
        int rows = array.length;
        int cols = array[0].length;
        int row = 0,col = cols-1;
        while(row>=0&&col>=0){
            if(array[row][col]==target) return true;
            if(row+1<rows&&array[row+1][col]<=target){
                row = row+1;
            }else{
                col = col -1;
            }
        }           
        return false;
    }