Leet Code 74 Search a 2D Matrix

Stella981
• 阅读 521

写一个高效的算法,在 m × n 的二维矩阵中搜索一个值。矩阵有以下性质:

每一行从左到右为升序。

每一行的第一个数都比上一行最后一个数大。

例如,有以下矩阵:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

给定 target = 3,返回 true。

思路:二分法,目标值与 (m/2,n/2) 位置的值比较,如果相等则返回true,如果目标值小,则搜索矩阵中小于 (m/2,n/2) 的部分,否则搜索矩阵中大于 (m/2,n/2) 的部分。

public class Solution {
  public static boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
      return false;
    }
    return searchMatrix(matrix, 0, 0, matrix.length - 1, matrix[0].length - 1,
        target);
  }

  private static boolean searchMatrix(int[][] matrix, int top, int left,
      int bottom, int right, int target) {
    if (top == bottom && left == right) {
      return matrix[top][left] == target;
    }
    int row = (top + bottom) >> 1;
    int col = (left + right) >> 1;
    if (matrix[row][col] < target) {
      if (row + 1 <= bottom) {
        if (searchMatrix(matrix, row + 1, left, bottom, col, target)) {
          return true;
        }
      }
      if (col + 1 <= right) {
        if (searchMatrix(matrix, row, col + 1, bottom, right, target)) {
          return true;
        }
      }
      return false;
    } else if (matrix[row][col] > target) {
      if (col - 1 >= left) {
        if (searchMatrix(matrix, top, left, row, col - 1, target)) {
          return true;
        }
      }
      if (row - 1 >= top) {
        return searchMatrix(matrix, top, col, row - 1, right, target);
      } else {
        return false;
      }
    } else {
      return true;
    }
  }

}
点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Karen110 Karen110
2年前
一篇文章带你了解JavaScript日期
日期对象允许您使用日期(年、月、日、小时、分钟、秒和毫秒)。一、JavaScript的日期格式一个JavaScript日期可以写为一个字符串:ThuFeb02201909:59:51GMT0800(中国标准时间)或者是一个数字:1486000791164写数字的日期,指定的毫秒数自1970年1月1日00:00:00到现在。1\.显示日期使用
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Java修道之路,问鼎巅峰,我辈代码修仙法力齐天
<center<fontcolor00FF7Fsize5face"黑体"代码尽头谁为峰,一见秃头道成空。</font<center<fontcolor00FF00size5face"黑体"编程修真路破折,一步一劫渡飞升。</font众所周知,编程修真有八大境界:1.Javase练气筑基2.数据库结丹3.web前端元婴4.Jav
Peter20 Peter20
2年前
mysql中like用法
like的通配符有两种%(百分号):代表零个、一个或者多个字符。\(下划线):代表一个数字或者字符。1\.name以"李"开头wherenamelike'李%'2\.name中包含"云",“云”可以在任何位置wherenamelike'%云%'3\.第二个和第三个字符是0的值wheresalarylike'\00%'4\
DaLongggggg DaLongggggg
2年前
python刷题-数列特征
问题描述给出n个数,找出这n个数的最大值,最小值,和。输入格式第一行为整数n,表示数的个数。第二行有n个数,为给定的n个数,每个数的绝对值都小于10000。输出格式输出三行,每行一个整数。第一行表示这些数中的最大值,第二行表示这些数中的最小值,第三行表示这些数的和。样例输入513245样例输出5211数据规模与约定1<n<10000。
Karen110 Karen110
2年前
人工智能数学基础-线性代数4:矩阵及矩阵运算
一、矩阵定义矩阵(Matrix)是一个按照长方阵列排列的复数或实数集合,定义如下:由m×n个数aij排成的m行n列的数表称为m行n列的矩阵,简称m×n矩阵。记作:这m×n个数称为矩阵A的元素,简称为元,数aij位于矩阵A的第i行第j列,称为矩阵A的(i,j)元,以数aij为(i,j)元的矩阵可记为(aij)或(aij)m×n,m×
Stella981 Stella981
2年前
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解
Opencv中Mat矩阵相乘——点乘、dot、mul运算详解2016年09月02日00:00:36 \牧野(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fme.csdn.net%2Fdcrmg) 阅读数:59593
Wesley13 Wesley13
2年前
1050 螺旋矩阵
1050 螺旋矩阵 (25分)本题要求将给定的 N 个正整数按非递增的顺序,填入“螺旋矩阵”。所谓“螺旋矩阵”,是指从左上角第1个格子开始,按顺时针螺旋方向填充。要求矩阵的规模为 m 行 n 列,满足条件:m×n 等于 N;m≥n;且 m−n 取所有可能值中的最小值。输入格式:输入在第1行中给出一个正整数 N,第2行给出 N
Wesley13 Wesley13
2年前
ES6 新增的数组的方法
给定一个数组letlist\//wu:武力zhi:智力{id:1,name:'张飞',wu:97,zhi:10},{id:2,name:'诸葛亮',wu:55,zhi:99},{id:3,name:'赵云',wu:97,zhi:66},{id:4,na