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

2024-03-25 15:36

本文主要是介绍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;}
};

这篇关于leetcode LCR121.寻找目标值-二维数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/845444

相关文章

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

CSS3 最强二维布局系统之Grid 网格布局

《CSS3最强二维布局系统之Grid网格布局》CS3的Grid网格布局是目前最强的二维布局系统,可以同时对列和行进行处理,将网页划分成一个个网格,可以任意组合不同的网格,做出各种各样的布局,本文介... 深入学习 css3 目前最强大的布局系统 Grid 网格布局Grid 网格布局的基本认识Grid 网

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2

vue如何监听对象或者数组某个属性的变化详解

《vue如何监听对象或者数组某个属性的变化详解》这篇文章主要给大家介绍了关于vue如何监听对象或者数组某个属性的变化,在Vue.js中可以通过watch监听属性变化并动态修改其他属性的值,watch通... 目录前言用watch监听深度监听使用计算属性watch和计算属性的区别在vue 3中使用watchE

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c