剑指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/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月3日 22:32
下一篇 2020年4月4日 19:55

相关推荐

  • leetcode636-函数的独占时间

    原题 给出一个非抢占单线程CPU的 n 个函数运行日志,找到函数的独占时间。 每个函数都有一个唯一的 Id,从 0 到 n-1,函数可能会递归调用或者被其他函数调用。 日志是具有以…

    算法 2020年2月2日
    0190
  • leetcode142-环形链表II

    原题 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始…

    2019年12月14日
    0420
  • leetcode78-子集

    原题 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。 说明: 解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3…

    算法 2020年5月24日
    0300
  • leetcode136-只出现一次的数字

    原题 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗…

    算法 2019年12月18日
    0130
  • leetcode1413-逐步求和得到正数的最小值

    原题 给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。 你需要从左到右遍历 nums 数组,并将 startValue 依次累加上 nums…

    算法 2020年6月21日
    02900
  • leetcode695-岛屿的最大面积

    原题 给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围…

    算法 2020年3月15日
    01220
  • leetcode912-排序数组

    原题 给定一个整数数组 nums,将该数组升序排列。 示例 1: 输入: [5,2,3,1] 输出: [1,2,3,5] 示例 2: 输入: [5,1,1,2,0,0] 输出: […

    算法 2020年3月31日
    0340
  • leetcode45-跳跃游戏II

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 示例: 输…

    算法 2020年2月15日
    0130
  • leetcode1371-每个元音包含偶数次的最长子字符串

    原题 给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 'a','e','i','o','u' ,在子字符串中都恰好出现了偶数次。 示例 1: 输入…

    算法 2020年5月20日
    01540
  • leetcode387-字符串中的第一个唯一字符

    原题 给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。 案例: s = "leetcode" 返回 0. s = "loveleetcode"…

    算法 2019年12月22日
    0120

发表回复

登录后才能评论