搜索二维矩阵[中等]

时间:2024-02-11 23:37:19 标签:  矩阵  

一、题目

给你一个满足下述两条属性的m x n整数矩阵:
【1】每行中的整数从左到右按非严格递增顺序排列。
【2】每行的第一个整数大于前一行的最后一个整数。

给你一个整数target,如果target在矩阵中,返回true;否则,返回false

示例 1:

输入: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出: true

示例 2:

输入: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出: false

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

二、代码

【1】两次二分查找: 由于每行的第一个元素大于前一行的最后一个元素,且每行元素是升序的,所以每行的第一个元素大于前一行的第一个元素,因此矩阵第一列的元素是升序的。

我们可以对矩阵的第一列的元素二分查找,找到最后一个不大于目标值的元素,然后在该元素所在行中二分查找目标值是否存在。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int low = 0, high = m * n - 1;while (low <= high) {int mid = (high - low) / 2 + low;int x = matrix[mid / n][mid % n];if (x < target) {low = mid + 1;} else if (x > target) {high = mid - 1;} else {return true;}}return false;}
}

时间复杂度: O(log ⁡m+log ⁡n)=O(log ⁡mn),其中mn分别是矩阵的行数和列数。
空间复杂度: O(1)

【2】一次二分查找: 若将矩阵每一行拼接在上一行的末尾,则会得到一个升序数组,我们可以在该数组上二分找到目标元素。代码实现时,可以二分升序数组的下标,将其映射到原矩阵的行和列上。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int low = 0, high = m * n - 1;while (low <= high) {int mid = (high - low) / 2 + low;int x = matrix[mid / n][mid % n];if (x < target) {low = mid + 1;} else if (x > target) {high = mid - 1;} else {return true;}}return false;}
}

时间复杂度: O(log⁡mn),其中mn分别是矩阵的行数和列数。
空间复杂度: O(1)

两种方法殊途同归,都利用了二分查找,在二维矩阵上寻找目标值。值得注意的是,若二维数组中的一维数组的元素个数不一,方法二将会失效,而方法一则能正确处理。

来源:分享自作者个人站点/博客

智能推荐

一、题目 给你一个满足下述两条属性的m x n整数矩阵&#xff1a; 【1】每行中的整数从左到右按非严格递增顺序排列。 【2】每行的第一个整数大于前一行的最后一个整数。 给你一个整数

标签:矩阵  

给你一个满足下述两条属性的 m x n 整数矩阵&#xff1a; 每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target &#xff0c;如果 target 在矩阵中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a;

标签:矩阵  

前言我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。LeetCode 算法到目前我们已经更新了 73 期,我们会保持更新时间和进度(周一、周三、周五早上 9:00 发布),每期的内容不多,我们希望大家可以在上班路上阅读,长久积累会有很大提升。不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。难度水平:中等

标签:矩阵  LeetCode  

一、题目大意标签:数组https://leetcode.cn/problems/search-a-2d-matrix-ii编写一个高效的算法来搜索&nbsp;m&nbsp;x&nbsp;n&nbsp;矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例 1:输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,

标签:矩阵  LeetCode  Search  II  MATRIX  

1.问题描述 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&#xff1a; 每行的元素从左到右升序排列。每列的元素从上到下升序排列。

标签:矩阵  

1.问题描述编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例:

标签:矩阵  II  LeetCode  

一、题目 1、题目描述 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

标签:矩阵  

题目描述 给你一个满足下述两条属性的 m x n 整数矩阵&#xff1a; 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target &#

标签:矩阵  

不难想到二分查找的思想&#xff0c;但是这道题目还可以利用有序大大减少代码量

标签:矩阵  

给你一个满足下述两条属性的 m x n 整数矩阵&#xff1a; 每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target &#xff0c;如果 target 在矩阵中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a;

标签:矩阵  

题目描述 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&#xff1a; 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。

标签:矩阵  

Problem: 240. 搜索二维矩阵 II

标签:矩阵  

240.搜索二维矩阵Ⅱ 编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&#xff1a;

标签:矩阵  

题目描述 力扣地址 给你一个满足下述两条属性的 m x n 整数矩阵&#xff1a; 每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target &#xff0c;如果 target 在矩阵中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a;

标签:高效  

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java

标签:数据结构  

一、题目大意https://leetcode.cn/problems/range-sum-query-2d-immutable给定一个二维矩阵 matrix,以下类型的多个请求:计算其子矩形范围内元素的总和,该子矩阵的 左上角 为 (row1, col1) ,右下角 为 (row2, col2) 。实现 NumMatrix 类:NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (ro

标签:矩阵  区域  Range  LeetCode  immutable  

给定一个二维矩阵 matrix&#xff0c;以下类型的多个请求&#xff1a; 计算其子矩形范围内元素的总和&#xff0c;该子矩阵的左上角为 (row1, col1) &#xff0c;右下角为 (row2, col2) 。 实现 NumMatrix 类&#xff1a; NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化 int sumRegion(int row1, int col1, int row2, int

标签:矩阵  

这是数组的第11篇算法&#xff0c;力扣链接。 给定一个二维矩阵 matrix&#xff0c;以下类型的多个请求&#xff1a; 计算其子矩形范围内元素的总和&#xff0c;该子矩阵的 左上角 为 (row1, col1) &#xff0c;右下角 为 (row2, col2) 。 实现 NumMatrix 类&#xff1a; NumMatrix(int[][] matrix)

标签:数组  

题目&#xff1a;给定一个九行九列矩阵&#xff0c;填充矩阵元素&#xff0c;要求&#xff1a; 1、每一行每一列&#xff0c;每个小九宫格&#xff08;图片画粗的地方就是&#xff09;不能包含相同元素 2、每一行&#xff0c;每一列&#xff0c;每个小九宫格均会完整出现1-9的数字  思路

标签:矩阵  

一、题目大意标签: 动态规划https://leetcode.cn/problems/01-matrix给定一个由 0 和 1 组成的矩阵 mat&nbsp;,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。两个相邻元素间的距离为 1 。示例 1:

标签:矩阵  LeetCode  MATRIX  

目录 1. 题目描述2. 常见错误思路3. 分析3.1 特例分析3.2 规律总结 4. 完整代码

标签:矩阵  

1&#xff09;二维矩阵代码 clear allclc% 定义目标函数fun

标签:矩阵  

700 二叉搜索树中的搜索 给定二叉搜索树&#xff08;BST&#xff09;的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在&#xff0c;则返回 NULL。 例如&#xff0c;

标签:二叉树  

题目1&#xff1a;654 最大二叉树 题目链接&#xff1a;654 最大二叉树 题意 根据不重复的整数数组nums构建最大的二叉树 &#xff0c;根节点是数组中的最大值&#xff0c;最大值左边的子数组构建左子树&#xff0c;最大值右边的子数组构建右子树 nums数组中最少含有1个元素&#xff0c;并且nums中的元素数值均大于等于0 递归  递归三部曲&#xff1a;

标签:二叉树  

猜你喜欢

这篇文章的题目稍微难一点 题目建议&#xff1a;  本题关键还是在转圈的逻辑&#xff0c;在二分搜索中提到的区间定义&#xff0c;在这里又用上了。  一、59. 螺旋矩阵 II 题目&#xff1a; 给你一个正整数 n &#xff0c;生成一个包含 1 到 n2 所有元素&#xff0c;且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1&#xff1a;

标签:螺旋  

力扣2331.计算布尔二叉树值   深度搜索&#xff1a;是要进入最下面 二叉树直接往递归上去想&#xff08;易写&#xff0c;不易想&#xff09; public boolean evaluateTree(TreeNode root) {if(root.left&#61;&#61;null||root.right&#61;&#61;nul

标签:深度  

一、题目大意给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。一般来说,删除节点可分为两个步骤:首先找到需要删除的节点;如果找到了,删除它。示例 1:

标签:节点  LeetCode  delete  BST  Node  

目录1. 概述2. 详论2.1. 行主序与列主序列2.2. 矩阵乘法3. 参考1. 概述three.js中自带了矩阵运算库,不过在使用的过程中总是容易混淆。不知道是行主序还是列主序,前乘和后乘也很容易弄反。就在这里辨析一下。2. 详论2.1. 行主序与列主序列很早就知道OpenGL中使用的矩阵是列主序,而Direct3D中使用的是行主序,但是没什么具体的体会,还直接弄混淆了。应该来说,无论Direct3D还是Op

标签:矩阵  JS  

目录 一、初等行变换 行阶梯 / 行最简 性质 

标签:线性代数  

矩阵与矩阵相乘遵循特定的数学规则。为了相乘&#xff0c;第一个矩阵的列数必须等于第二个矩阵的行数。矩阵乘法的结果是一个新矩阵&#xff0c;其行数等于第一个矩阵的行数&#xff0c;列数等于第二个矩阵的列数。矩阵乘法不满足交换律&#xff0c;即 AB≠BA。 例

标签:矩阵  

题目1&#xff1a;235 二叉搜索树的最近公共祖先 题目链接&#xff1a;235 二叉搜索树的最近公共祖先 题意 找出二叉搜索树中两个指定节点的最近公共祖先 二叉搜索树中节点各不相同&#xff0c;且两个指定的节点均存在与二叉搜索树中&#xff0c;也不同 递归 递归三部曲&#xff1a; 1&#xff09;递归函数的参数和返回值

标签:节点  

邻接矩阵&#xff1a;很简单&#xff0c;就是两个点有关系就是1&#xff0c;没有关系就是0 可达性矩阵&#xff1a;非常简单&#xff0c;两点之间有路为1&#xff0c;没有路为0

标签:矩阵  

2024每日刷题&#xff08;110&#xff09; Leetcode—33. 搜索旋转排序数组

标签:数组  

标签:

[本节目标] 1. 二叉搜索树实现 2.二叉树搜索树应用分析 3. 二叉树进阶面试题 1. 二叉搜索树 1.1 二叉搜索树概念 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的二叉树: 若它的左子树不为空&#xff0c;则左子树上所有节点的值都小于根节点的值若它的右子树不为空&#xff0c;则右子树上所有节点的值都

标签:

搜索技巧(二)搜索条件详解上回我们已经学习了一些简单的搜索功能,比如设置搜索语句、分页方法、数量查询以及高亮和折叠的查询效果。而今天,我们将更加深入地学习其它搜索相关的内容。最核心的,就是布尔查询,也就是类似于我们在数据库中的 AND 和 OR 之类的语法。不过在这之前,就像是 Explain 可以分析数据库的查询语句一样。XS 也为我们提供了一个可以查看分词结果以及

标签:详解  条件  技巧  

题目1&#xff1a;530 二叉搜索树的最小绝对差 题目链接&#xff1a;530 二叉搜索树的最小绝对差 题意 返回二叉搜索树的两个不同节点间的最小差值&#xff08;是一个正数&#xff0c;取绝对值&#xff09; 注意利用二叉搜索树的性质  中序遍历得到的是一个有序单调递增的数组 递归

标签:祖先  

学习目标&#xff1a; 博主介绍: 27dCnc 专题 : 数据结构帮助小白快速入门 &#x1f44d;&#x1f44d;&#x1f44d;&#x1f44d;&#x1f44d;&#x1f44d;&#x1f44d

标签:代码  

师从清风 矩阵的创建方法 在MATLAB中&#xff0c;矩阵的创建方法主要有三种&#xff0c;分别是&#xff1a;直接输入法、函数创建法和导入本地文件中的数据。 直接输入法 输入矩阵时要以中括号“[ ]”作为标识符号&#xff0c;矩阵的所有元素必须都在中括号内。 矩阵的同行元素之间用空格或逗号分隔&#xff0c;行与行之间用分号或回车键分隔。 a &#61; [1 2 3; 4 5 6]b &#61; [1,2,3; 4,5,6]c &#61; [2  56  7]d &#61; [3 6;6

标签:矩阵  

在日常的工作和生活中,强大的分析能力成为专业人士的基本特征。那么,如何拥有强大的分析能力呢?&nbsp;对此,答案很多。比如,丰富的知识储备、强大的逻辑思维能力、拥有批判性思维能力。这些因素对于成为专业人士非常重要,然而却不是一朝一夕才能拥有。对于普通人而言,学习像专业人士那样使用一些分析工具,或许会事半功倍。因此,接下来我将会介绍一些实用的思维模式。今天我先介绍矩阵分析法。

标签:脚手架  矩阵  分析法  思维  笔记  

二叉树part08 235.二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点 235. 二叉搜索树的最近公共祖先 方法一&#xff

标签:节点  

二叉树part08 235.二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点 235. 二叉搜索树的最近公共祖先 方法一&#xff1a;递归法&#xff08;利用二叉搜索树性质&#xff09;

标签:节点  

完整代码在最后 树结构&#xff1a; 1.树结构本身是一种天然的组织结构 2.高效 二

标签:java  

目录 前言&#xff1a;  1.二叉搜索树 1.

标签:二叉树  

目录1. 概述2. 详解1. 概述使用如下代码绘制一个面:use strict;function init() { //console.log(Using Three.js version: + THREE.REVISION); // create a scene, that will hold all our elements such as objects, cameras and lights. var scene = new THREE.Scene()

标签:矩阵  JS  

一、审题 时间限制&#xff1a;1000ms                内存限制&#xff1a;256MB                各平台平均AC率&#xff1a;14.89% 题目描述 输出一个n*n大小的螺旋矩阵。 螺旋矩阵的样子&#xff1a;

标签:矩阵  

文章目录 题目链接题目描述解题思路代码实现总结 题目链接 链接: P1101 单词方阵

标签:方阵  

作者推荐 【动态规划】C&#43;&#43;算法312 戳气球 题目 给定一个 m x n 整数矩阵 matrix &#xff0c;找出其中 最长递增路径 的长度。 对于每个单元格&#xff0c;你可以往上&#xf

标签:矩阵  

相关问题

相关文章

热门文章

推荐文章

相关标签