(数组与矩阵) 剑指 Offer 04. 二维数组中的查找 ——【Leetcode每日一题】

news/2024/2/28 18:45:17

❓ 剑指 Offer 04. 二维数组中的查找

难度:中等

在一个 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 <= n <= 1000 0<=n<=1000
  • 0 < = m < = 1000 0 <= m <= 1000 0<=m<=1000

注意:本题与 240. 搜索二维矩阵 II 相同。

💡思路:

由于每行的元素从左到右升序排列,每列的元素从上到下升序排列,所以对于矩阵中的任意一个数都比其左上角上的数大,都比其右下角的小,所以target如果在两个对角之间,则一定在该对角之间的左下角或右上角;

  • 从而我们可以在矩阵的左下角开始判断,答案一定在右上角
    • 如果当前数等于target,则找到,返回true
    • 如果当前数小于target,则往右查找,列号 +1;
    • 如果当前数大于target,则往上查找,行号 -1

🍁代码:(C++、Java)

C++

class Solution {
public:bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {int i = matrix.size() - 1, j = 0;while(i >= 0 && j < matrix[0].size()){if(target == matrix[i][j]) return true;else if(target > matrix[i][j]) j++;else i--;}return false;}
};

Java

class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {int i = matrix.length - 1, j = 0;while(i >= 0 && j < matrix[0].length){if(target == matrix[i][j]) return true;else if(target > matrix[i][j]) j++;else i--;}return false;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( n + m ) O(n + m) O(n+m),在搜索的过程中,如果我们没有找到 target,那么我们要么将 i 减少 1,要么将 y 增加 1。由于 (i, j) 的初始值分别为 (n - 1, 0),因此 i 最多能被减少 n 次,j 最多能被增加 m 次,总搜索次数为 n+m。在这之后,ij 就会超出矩阵的边界。

  • 空间复杂度 O ( 1 ) O(1) O(1)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/911728.html

相关文章

绝对值得收藏的十位电影配乐大师 (中)

TOP5&#xff1a;如日中天的配乐大师——汉斯.季默Hans Zimmer 汉斯.季默是最近最如日中天、炙手可热的电影配乐大师之一&#xff0c;《角斗士》配乐尽管在奥斯卡提名中被《卧虎藏龙》夺去&#xff0c;但影片中令人窒息的英雄主义诗篇的音乐给人留下非常深刻的印象。 汉斯…

轻音乐

轻音乐&#xff0c;是指那种风格轻松、活泼的音乐&#xff0c;它是能给人以愉悦和抒情感&#xff0c;优美动听、通俗易懂的音乐。所谓“轻”&#xff0c;是指与庄重的严肃音乐对比而言。舞曲、进行曲、小夜曲比奏鸣曲、交响曲更“轻”&#xff1b;轻歌曲、抒情歌曲、诙谐歌曲比…

总觉得晚上的时间

总觉得晚上的时间&#xff0c;要好好珍惜。 晚上杂事不少&#xff0c;所以很久没有静下心来听音乐了。 不关注流行音乐&#xff0c;也不知去哪寻找特别对自己口味的音乐类型&#xff0c;以往喜欢重金属&#xff0c;来去就听一下Rammstein或Guns nroses等&#xff0c;特别是Ramm…

打篮球,听摇滚,敲键盘也能是人生赢家。程序员访谈(三)

点击上方关注我们&#xff0c;让小care关爱你&#xff01; 自从有了人类的存在&#xff0c;就处处存在着偏见。总有些人认为&#xff0c;程序员只会“敲代码”跟“修电脑”。 其实有些程序员可能并不会修电脑&#xff0c;而有些程序员也是一个很酷的人。 走近生活&#xff0c;梦…

【linux内核】查看和清空kernel日志

用dmesg 查看 dmesg dmesg|tail -n 8 清空 dmesg -c 用/var/log/kern.log 查看 cat /var/log/kern.log 清空 >/var/log/kern.log 参考&#xff1a; Linux 命令&#xff08;160&#xff09;—— dmesg 命令_dmesg命令详解_恋喵大鲤鱼的博客-CSDN博客 linux kernel…

计算机语言词汇量,词汇量最多的10种语言,会一种算你赢!

原标题&#xff1a;词汇量最多的10种语言&#xff0c;会一种算你赢&#xff01; 沪江法语君按&#xff1a;我会……种。 Pas forcment la langue la plus difficile apprendre (quoi que) mais celle dont les dictionnaires sont les plus pais. Le franaisest-il dans le cl…

Native Instruments Guitar Rig 5 Player WiN-MAC 免费的电吉他效果器

免费、可扩展的效果器引擎&#xff0c;配备一个放大器&#xff0c;17种音响效果&#xff0c;13个效果器和调节器。简单易用。 免费的箱头模拟以及效果器机架 基于GUITAR RIG 5 PRO 箱头模拟将伴随着成套的箱体&#xff0c;3款效果器以及50个随时可用的预设。 这也包含着 KOMPLE…

【电子学会】2023年05月图形化四级 -- 计算圆的面积和周长

计算圆的面积和周长 编写程序计算圆的面积和周长。输入圆的半径&#xff0c;程序计算出圆的面积和周长&#xff0c;圆的面积等于3.14*半径*半径&#xff1b;圆的周长等于2*3.14*半径。 1. 准备工作 &#xff08;1&#xff09;保留舞台中的小猫角色和白色背景&#xff1b; 2…

有关英文单词中间有空格问题的解决

相信很多人在码代码的时候&#xff0c;会出现代码的英文单词突然出现空格&#xff0c;以下为解决方式&#xff1a; 1、很多人都说shift空格键&#xff0c;大家可以试试&#xff0c;但对于我来说不好使&#xff1b; 2、原因其实很简单&#xff0c;就是输入法的问题&#xff1a…

Skywalking使用说明

需求背景 随着分布式的盛行&#xff0c;系统的复杂度也逐步增加&#xff0c;不同服务间的交互对性能的定位提出了更高的要求。任意一个节点的异常&#xff0c;都可能对业务系统造成损失。对于链路追踪&#xff0c;迫切需要一个优秀的监测工具。 需求如下 功能性需求 请求链路追…

正则表达式 中文 英文 空格

[\u4e00-\u9fa5]/g;中文正则表达式 [a-zA-Z]/g;//英文正则表达式 /\s/g;//空格

搜狗输入法取消英文空格确认

在使用搜狗输入法时&#xff0c;对于中文&#xff0c;按空格键确认&#xff0c;然后打印在屏幕上。 但是对于英文&#xff0c;不想这样麻烦啊&#xff0c;只想输入一个字母&#xff0c;屏幕上显示一个字母。 搜狗输入法的设置如下&#xff0c;就ok 了。 详细解释&#xff0c;…

Word如何删除中英文混排中中文间的多余空格

如何快速批量删除word中多余的空格呢&#xff0c;尤其是中英文混排的文档&#xff0c;有时会有连续的多个空格&#xff0c;如何去掉中文中的空格&#xff0c;同时保留英语单词间的空格呢。今天就和朋友们说说去掉word中空格的简单好用的方法吧&#xff01; 1、选中需要去多个空…

win10更改ctrl+空格切换中英文

win10更改ctrl空格切换中英文 重启电脑后生效 因为众多IDE的代码提示快捷键都是ctrlspace(ctrl空格)&#xff0c;但是win10系统自带的切换中英文的快捷键也是这个&#xff0c;这就造成在IDE中使用这个快捷键无法提示代码补全&#xff0c;所以更改系统的快捷键设置。 打开设置点…

输入一个英文语句,每个单词用空格隔开

//输入一个英文语句&#xff0c;每个单词用空格隔开。保证输入只包含空格和字母。 package demo0424; import java.util.*; import java.io.*; public class Main{public static void main(String[] args)throws Exception{BufferedReader br new BufferedReader(new InputSt…

浪潮服务器键盘自动输空格,键盘空格键的常用技巧分享

1、常用的播放应用程序&#xff0c;其中包括音乐播放、视频播放等应用程序&#xff0c;比如在我们观看电影的一些播放器&#xff0c;还是网站上的在线观看&#xff0c;都是通过空格键来对控制暂停\播放的操作。就我们很常用的酷狗和qq音乐都是通过敲击空格键来控制暂停\播放的设…

vscode输入英文时字体之间的间隔突然变大

主要原因&#xff1a; vscode&#xff08;其他编译软件&#xff09;的快捷键和输入法快捷键冲突了。 正常情况全角就是字母和数字等与汉字占等宽位置的字。 半角就是ASCII方式的字符&#xff0c;在没有汉字输入法起作用的时候输入的字母数字和字符都是半角的。 由于冲突使得英文…

空格键除了敲空格外的多种用途

在很多人的印象中&#xff0c;只要提到电脑上的空格键&#xff0c;第一直觉是只有在编辑文字、玩游戏的时候用到它&#xff0c;其他方面的用途似乎用到的情况并不多&#xff0c;可空格键不只限于敲空格&#xff0c;其实它还隐藏了多种用途&#xff0c;今天我们就来跟大家聊一下…

Visual Studio中输入英文会在字母之间自动增加空格

现象 不小心按了什么键之后字母之间增加了空格&#xff0c;如下面&#xff1a; ![在这里插入图片描述](https://img-blog.csdnimg.cn/b211b973b9c8470fae4402161ddb3935.png 解决办法 针对上面图片中显示的这种英文字母之间出现空格&#xff0c;是输入法出现了问题。恢复的…

计算机空格键作用,电脑空格键有哪些作用?你知道几个?

我们在操作电脑时经常会用到空格键&#xff0c;打字基本都用它来当确定键&#xff0c;但你真正了解空格键的妙用吗&#xff1f;空格键所占空间那么大&#xff0c;肯定是不止一种作用了&#xff0c;今天我们就来说说说键盘上空格键的用处&#xff01; 电脑空格键有哪些作用&…
最新文章