首页 > 试题广场 >

二维数组中的查找

[编程题]二维数组中的查找
  • 热度指数:2367260 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
在一个二维数组array中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]

给定 target = 7,返回 true。

给定 target = 3,返回 false。

数据范围:矩阵的长宽满足 , 矩阵中的值满足
进阶:空间复杂度 ,时间复杂度
示例1

输入

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

true

说明

存在7,返回true   
示例2

输入

1,[[2]]

输出

false
示例3

输入

3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

false

说明

不存在3,返回false   
头像 漫漫云天自翱翔
发表于 2021-07-16 02:04:54
精华题解 题解一:暴力搜索解题思路: 逐行逐列的搜索二维数组,判断是否存在目标值。 复杂度分析:时间复杂度:O(MN)空间复杂度:O(1) 实现如下: class Solution { public: bool Find(int target, vector<vector<int> 展开全文
头像 牛客题解官
发表于 2022-04-22 11:39:55
精华题解 题目的主要信息: 矩阵的行元素和列元素都是有序的,从左到右递增,从上到下递增,完全递增元素不会有重复 找到矩阵中有没有给定元素即可 举一反三: 学习完本题的思路你可以解决如下题目: BM17.二分查找-I BM19.寻找峰值 BM21.旋转数组 方法:二分查找(推荐使用) 知识点:分治 分治即“ 展开全文
头像 漫漫云天自翱翔
发表于 2021-06-23 10:28:07
精华题解 题解一:暴力搜索解题思路: 逐行逐列的搜索二维数组,判断是否存在目标值。 复杂度分析:时间复杂度:O(MN)空间复杂度:O(1) 实现如下: class Solution { public: bool Find(int target, vector<vector<int> 展开全文
头像 蒙牛麦片
发表于 2021-07-16 18:01:47
精华题解 NC29 矩阵查找 题意分析: 实现一个对有序矩阵查找函数 题解一(暴力查找): 对矩阵的每一行进行查找,由于矩阵的每一行都是有序的,因此我们可以对每一行进行二分查找。 代码实现如下 bool searchMatrix(vector<vector<int> >& ma 展开全文
头像 Peterliang
发表于 2021-07-18 14:55:21
精华题解 题意分析 给我们一个二维数组,这个二维数组从上到下,从左到右都是递增的,需要我们判断这个二维数组中是否存在一个给定的数字。如果存在,那么直接返回true,否则返回false 思路分析 思路一 暴力法 我们可以对这个二维数组直接进行遍历,然后我们逐个进行判断是否存在,如果存在直接返回true,最 展开全文
头像 Maokt
发表于 2021-06-29 15:31:47
精华题解 算法思想一:暴力遍历 解题思路: 如果不考虑二维数组排好序的特点,则直接遍历整个二维数组的每一个元素,判断目标值是否在二维数组中存在。 依次遍历二维数组的每一行和每一列。如果找到一个元素等于目标值,则返回 true。如果遍历完毕仍未找到等于目标值的元素,则返回 false。 代码 展开全文
头像 牛客题解官
发表于 2020-05-26 11:36:48
题目难度:二星 考察点:数组,二分查找 简要说明:这是一道对二维数组进行二分查找的算法,考察对二分查找的灵活运用。 方法1: 暴力算法 分析:直接遍历一遍数组,即可判断目标target是否存在。 复杂度分析时间复杂度:O(n^2),因为最坏情况下,数组中的元素都需要遍历一次。空间复杂度:O(1) 展开全文
头像 叫我皮卡丘
发表于 2019-08-08 16:59:32
【剑指 offer】二维数组中的查找 -- Java 实现 一、暴力法 1. 分析 挨个遍历数组,如果找到就返回 true 2. 代码 public class Solution { public boolean Find(int target, int [][] array) { 展开全文
头像 凉风起天末
发表于 2019-08-13 22:51:14
分享五种解题方法,仅为拓宽思路:(注:如果代码出现了段错误问题,可能是没有考虑到空数组,健壮性也是算法的一部分) 一、左下/右上元素移动法:十分简单巧妙,在看了徘徊的路人甲的题解才后知后觉;设M=min(m,n),N=max(m,n),复杂度为O(N),详见链接题解:链接:https://www.n 展开全文
头像 把牛妹带回家
发表于 2019-07-26 15:35:13
重点: 数组为空 排好序 上面行的右边的数也可以比下面行左边的数大 顺序查找 def Find(self, target, array): # write code here if len(array)==0 or len(array[0])==0: r 展开全文
头像 没有人比我更菜
发表于 2019-12-03 21:18:10
二分查找法: O(logM * logN) 题目描述 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 [ [1, 4, 7, 11, 15], 展开全文
头像 Oh~Sunny
发表于 2019-12-27 19:58:53
# -*- coding:utf-8 -*- class Solution: # array 二维列表 def Find(self, target, array): # write code here #方法二 从右上角开始进行搜索 展开全文
头像 心谭
发表于 2019-12-20 11:35:14
【JavaScript】-剑指offer-二维数组中的查找 解法 1:暴力法 遍历数组中的所有元素,找到是否存在。 时间复杂度是 O(N^2),空间复杂度是 O(1) // ac地址:https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70 展开全文
头像 霜降_
发表于 2022-02-21 19:29:50
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param target int整型 # @param array int整型二维数组 # @return bool布尔型 # class Solution: def Find(self , 展开全文
头像 数据结构和算法
发表于 2020-08-07 13:01:53
剑指 Offer 4. 二维数组中的查找 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 答案: 1,暴力求解 当然最容易想到的是暴力求解,就是一个个 展开全文
头像 道阻且长z
发表于 2019-09-01 14:32:46
思路: 暴力解法:对数组第一行进行二分查找,再对数组第二行进行二分查找。 矩阵是有序的:利用二维数组由上到下,由左到右递增的规律。那么选取右上角或者左下角的元素a[row][col]与target进行比较,当target小于元素a[row][col]时,那么target必定在元素a所在列的左边,即 展开全文