leetcode LCR121.寻找目标值-二维数组

目录

  • 问题描述
  • 示例
  • 具体思路
    • 思路一
    • 思路二
  • 代码实现

问题描述

m*n 的二维数组 plants 记录了园林景观的植物排布情况,具有以下特性:

  • 每行中,每棵植物的右侧相邻植物不矮于该植物;
    每列中,每棵植物的下侧相邻植物不矮于该植物。

题目链接:https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/description/

示例

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
相似题目链接(与leetcode 240题相同): https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

具体思路

  这个题目和杨氏矩阵是一样的。
  杨氏矩阵:有一个二维数组,数组的每行从左到右都是递增的,每列从上到下都是递增的,在这样的数组中查找一个数字是否存在。
例如有一个矩阵为:
1 2 3
4 5 6
7 8 9

思路一

  直接对该二维数组进行遍历,但该种方法的时间复杂度为 O ( N 2 ) O(N^2) O(N2),在此不考虑。

思路二

  我们可以找到行列的交界处,比如[0][2],即数字3这个位置,通过观察,我们可以发现,该数字是所在行中的最大数字,所在列中的最小数字,可以用目标数target和该交界处数字进行比较,如果target大于该数,则表示比这行最大的数还要大,所以一定不在这一行,舍弃该行,向下行进行查找。 如果target小于该数,则表示target比这列最小的数还要小,所以一定不在这一列,舍弃该列,向左边行进行查找。依次类推,找到返回true,找不到返回false
在这里插入图片描述

如果用[2][0]也是可以的,思路则反过来。
在这里插入图片描述

代码实现

class Solution {
public:bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {//需要考虑输入为空数组时的判断,如果是空数组的话无法对其进行访问if (plants.size() == 0 || plants[0].size() == 0) //plants.size()表示是有几个vector<int>(行),plants[0].size()表示第0个vector里面有多少个元素(列){return false;}int i = 0;   //二维数组的第0行int j = plants[0].size() - 1;  //二维数组第0行的最后一个元素下标while (i < plants.size() && j >= 0){if (target < plants[i][j])  //目标值比第0行最后一个元素小就往左边进行查找{j--;}else if (target > plants[i][j]) //目标值比第0行最后一个元素大就往下查找{i++;}else{return true;}}return false;}
};
class Solution {
public:bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {int i = plants.size() - 1, j = 0;   //最后一行的第1个元素while (i >= 0 && j < plants[0].size()){if (plants[i][j] > target) i--;else if (plants[i][j] < target) j++;else return true;}return false;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/285603.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Hive SQL必刷练习题:留存率问题(*****)

留存率&#xff1a; 首次登录算作当天新增&#xff0c;第二天也登录了算作一日留存。可以理解为&#xff0c;在10月1号登陆了。在10月2号也登陆了&#xff0c;那这个人就可以算是在1号留存 今日留存率 &#xff08;今日登录且明天也登录的用户数&#xff09; / 今日登录的总…

一些恶意样本的流量分析学习

Trickbot Trickbot 是一种自 2016 年以来一直在感染受害者的信息窃取者和银行恶意软件。Trickbot通过恶意垃圾邮件&#xff08;malspam&#xff09;分发&#xff0c;也由其他恶意软件&#xff08;如Emotet&#xff0c;IcedID或Ursnif&#xff09;分发。 分析来自恶意垃圾邮件…

银行5G短消息应用架构设计

&#xff08;一&#xff09;RCS简介 1.1 RCS的提出与标准制定 RCS(Rich Communication Services & Suite&#xff0c;富媒体通信)是GSMA(Groupe Speciale Mobile Association&#xff0c;全球移动通信系统协会)在2008年提出的一种通讯方式&#xff0c;RCS融合了语音、消息…

Bytebase 2.14.1 - 分支 (Branching) 功能支持 Oracle

&#x1f680; 新功能 分支 (Branching) 功能支持 Oracle。为 SQL 编辑器添加了项目选择器。 新增 SQL 审核规范&#xff1a; 禁止混合 DDL、DML 语句。禁止对同一张表进行不同类型的 DML 变更 (UPDATE,INSERT,DELETE)。 &#x1f514; 重大变更 工作空间设置中的「数据访问…

【已解决】MySQL:常用的除法运算+精度处理+除数为0处理

目录 问题现象&#xff1a; 问题分析&#xff1a; 拓展&#xff1a; 1、除法运算&#xff1a; 拓展&#xff1a;MySQL中常用的几种除法运算 1、取整除法 2、浮点数除法 3、取余除法 4、向上取整除法 5、向下取整除法 2、运算结果的精度处理 1.1、浮点数 1.2、总位数 1.3、…

电脑哥的励志创业路:蹭别人的电脑做抖店

我是王路飞。 没有一步到位的创业项目&#xff0c;也没有一击必中的解决方法&#xff0c;有的只是需要时刻解决的当下问题。 做事/创业/成长/生活/人生&#xff0c;都不要追求百分百的圆满&#xff0c;不要抱有一帆风顺的幻想&#xff0c;不要期待十全十美的结果。 它们的第…

Visual Studio QT6 工程引入组件模块,例如:QtXml

QT 工程引入 QtXml QT 版本 6.6.1 Visual Studio 版本 Microsoft Visual Studio Community 2022 (64 位) - Current 版本 17.7.5 打开 Visual Studio 项目工程选择 工具栏 - 扩展 - QT VS Tools -Qt Project Settings 勾选 xml 后点击确定 点击应用即可 注意&#xff1a;配置环…

day44 动态规划part6

完全背包 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品都有无限个&#xff08;也就是可以放入背包多次&#xff09;&#xff0c;求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同…

外部普米集中监控多个Prometheus实例:Prometheus Agent 模式与Prometheus 联邦模式 超级详细

外部普米集中监控多个Prometheus实例 Prometheus Agent 模式-使用推送方式来监控1.外部Prometheus配置1.需要开放端口&#xff0c;在启动时&#xff0c;需要配置开放监听端口2.添加prometheus启动参数3.修改配置后重启prometheus即可 2.各个节点的普米配置1.修改prometheus.yml…

HiveSQL一本通 - 案例实操

文章目录 0.HiveSQL一本通使用说明6.综合案例练习之基础查询6.1 环境准备创建数据表数据准备加载数据 6.2 简单查询练习1.查询姓名中带“山”的学生名单2.查询姓“王”老师的个数3.检索课程编号为“04”且分数小于60的学生的分数信息&#xff0c;结果按分数降序排列4.查询数学成…

vue.js——学习计划表

1&#xff09;准备工作 ①打开D:\vue\chapter02\ learning_schedule 目录&#xff0c;找到 index.html 文件。 在文件中引 入BootStrap 样式文件&#xff0c;具体代码如下 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8&qu…

【Linux】权限管理

文章目录 前言1.权限访问者的分类2.文件类型与访问权限3.文件权限值的表达方式4.文件访问权限的相关设置5.file指令6.目录权限理解与漏洞7.粘滞位的理解 前言 Linux下有两种用户&#xff1a;超级用户(root)和普通用户 超级用户&#xff1a;可以再linux系统下做任何事情&#x…

Vue3 + Vite + TS + Element-Plus + Pinia项目(3)--新建路由

1、在src文件夹下新建router文件夹后&#xff0c;创建index.ts文件 2、具体如下 import { createRouter, createWebHashHistory } from vue-routerconst router createRouter({history: createWebHashHistory(),routes: [{path: "/index",component: () > impor…

关于YOLOv9项目中使用已有模块自由改进的教程

专栏介绍&#xff1a;YOLOv9改进系列 | 包含深度学习最新创新&#xff0c;助力高效涨点&#xff01;&#xff01;&#xff01; 1. 文件说明 在YOLOv5-v9&#xff0c;模型的结构是以yaml文件的存储。我们可以在原有的yaml基础上增、减、改模块&#xff0c;创作我们自己的模型。 …

ASM四部曲之一:什么是ASM

文章目录 前言什么是.class文件什么是ASM概述作用域模型基于ASM的程序架构 ASM库结构 前言 本文翻译自ASM官方文档。 什么是.class文件 Java字节码文件&#xff08;.class&#xff09;是Java编译器编译Java源文件&#xff08;.java&#xff09;产生的目标文件。它是一种8位字…

基于SpringBoot+Layui的社区物业管理系统

项目介绍 社区物业管理系统是基于java程序开发,本系统分为业主和管理员两个角色 业主可以登陆系统,查看车位费用信息,查看物业费用信息,在线投诉,查看投诉,在线报修; 管理员可以车位收费信息,物业收费信息,投诉信息,楼宇信息,房屋信息,业主信息,车位信息,抄表信…

芯片设计工程师必备基本功——《Verilog+HDL应用程序设计实例精讲》

进入芯片行业需要学习哪些基本功呢&#xff1f;其实芯片设计工程师的技能是通过多年的经验学习的。在您开始作为芯片设计工程师工作之前&#xff0c;很难给出一个需要的全面的单一列表&#xff0c;也不可能学习所有内容。话虽如此&#xff0c;但您开始芯片设计师职业生涯时必须…

瑞萨杯(一)

基础信息 RA6M5&#xff1a;ARM V8架构&#xff0c;24MHz外置晶振&#xff0c;200MHz主频 SCI&#xff08;Serial Communications Interface&#xff09;&#xff0c;意为串行通信接口 参考链接&#xff1a; 【瑞萨RA系列FSP库开发】RASCKeil的环境搭建_瑞萨ra mdk-CSDN博客…

Web安全基础入门+信息收集篇

教程介绍 学习信息收集&#xff0c;针对域名信息,解析信息,网站信息,服务器信息等&#xff1b;学习端口扫描&#xff0c;针对端口进行服务探针,理解服务及端口对应关系&#xff1b;学习WEB扫描&#xff0c;主要针对敏感文件,安全漏洞,子域名信息等&#xff1b;学习信息收集方法…

【webpack】----错误解决【Cannot read properties of undefined (reading ‘tap‘)】

1. 报错场景 安装 webpack-obfuscator 后&#xff0c;进行 js 代码混淆编译的时候报错。 2. 报错截图 3. 错误原因 通常是由于版本不兼容或配置错误引起的。 4. 查询本地 webpack 版本 4.1 查询命令 npm 查询 npm view webpack versionyarn 查询 yarn info webpack ver…