剑指offer04-二维数组中的查找

原题(来源Leetcode)

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

示例:

现有矩阵 matrix 如下:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30] ]

给定 target = 5,返回 true

给定 target = 20,返回 false

限制:

0 <= n <= 1000

0 <= m <= 1000

注意: 本题与主站 240 题相同:https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

解法

思想

我用的dfs..思路比较清晰点。(不推荐)

官方给的题解思想(减而治之,标识数法)非常巧妙:可以从右上角或左下角开始线性搜索,因为右上角的元素为列开始的最大值,而左下角的元素为行开始的最大值。一旦这个数比要查找的数大,就可以排除这一行/这一列。

代码

dfs:

class Solution {
    int[][] matrixGlo;
    Boolean[][] dfs;
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix.length==0) return false;
        dfs = new Boolean[matrix.length][matrix[0].length];
        matrixGlo = matrix;
        return dfs(0,0,target);
    }

    public boolean dfs(int x,int y,int target){
        if(x>=matrixGlo.length||y>=matrixGlo[0].length) return false;
        if(dfs[x][y]!=null) return dfs[x][y];
        if(matrixGlo[x][y]>target) return false;
        if(matrixGlo[x][y]==target) return true;
        boolean result = dfs(x+1,y,target)||dfs(x,y+1,target);
        dfs[x][y] = result;
        return result;
    }
}

标识数法:(作者:liweiwei1419)

public class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int rows = matrix.length;
        if (rows == 0) {
            return false;
        }
        int cols = matrix[0].length;
        if (cols == 0) {
            return false;
        }
        // 从左下角开始查找
        int x = rows - 1;
        int y = 0;
        while (x >= 0) {
            while (y < cols && matrix[x][y] < target) {
                y++;
            }
            if (y < cols && matrix[x][y] == target) {
                return true;
            }
            x--;
        }
        return false;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer04-%e4%ba%8c%e7%bb%b4%e6%95%b0%e7%bb%84%e4%b8%ad%e7%9a%84%e6%9f%a5%e6%89%be/