牛客在线编程101-18 二维数组中的查找

电玩女神 2023-10-04 19:33 38阅读 0赞

### 题目 ###

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。  
\[  
\[1,2,8,9\],  
\[2,4,9,12\],  
\[4,7,10,13\],  
\[6,8,11,15\]  
\]  
给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 0 \\le n,m \\le 5000≤n,m≤500 ， 矩阵中的值满足 0 \\le val \\le 10^90≤val≤10  
9

进阶：空间复杂度 O(1)O(1) ，时间复杂度 O(n+m)O(n+m)

### 解析 ###

可以直接遍历整个数组，从左上角第一个数字开始，直到最后一个。这种方法没有用到数组递增的特性。对于一个有顺序的排列，可以尝试从中间的一个值开始，如果这个值大于目标值，则向数值小的方向继续寻找，否则向数值大的方向寻找。

public class Solution {
        
        public boolean Find(int target, int [][] array) {
        
            int row = array.length;
            int col = array[0].length;
            for (int i = row - 1, j = 0; i >= 0 && j < col;) {
        
                if (array[i][j] == target) {
        
                    return true;
                } else if (array[i][j] > target) {
        
                    i--;
                } else {
        
                    j++;
                }
            }
            
            return false;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，38人围观）

还没有评论，来说两句吧...

相关阅读

相关牛客网面试必刷：BM18 二维数组中的查找

牛客网面试必刷：BM18 二维数组中的查找前言一、解法1：逐行使用二分搜索二、解法2：线性搜索（推荐） --------------------

逃离我推掉我的手/ 2024年03月22日 15:49/ 0 赞/ 45 阅读

相关牛客在线编程101-18 二维数组中的查找

题目在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组

电玩女神/ 2023年10月04日 19:33/ 0 赞/ 39 阅读

相关牛客二维数组打印

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

墨蓝/ 2023年05月22日 11:28/ 0 赞/ 9 阅读

相关 php 二维数组中查找,二维数组中的查找

一、给出的是方阵 \[\[1,6,7,8\], \[3,7,8,9\], \[9,10,11,12\], \[12,13,14,15\]\] 这种情况非常简单，可知对

r囧r小猫/ 2023年01月14日 09:59/ 0 赞/ 157 阅读

相关二维数组中的查找

二维数组中的查找 1、参考资料 https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-l

旧城等待，/ 2022年12月02日 10:42/ 0 赞/ 184 阅读

相关牛客题霸 NC29 二维数组中的查找

https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e 解决方案 Go 版本一

向右看齐/ 2022年09月11日 04:09/ 0 赞/ 167 阅读

相关二维数组中的查找

题目要求如下: 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有

ゝ一世哀愁。/ 2022年06月16日 07:49/ 0 赞/ 212 阅读

相关二维数组中的查找

链接：[https://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e?orderByHo

野性酷女/ 2022年06月07日 01:59/ 0 赞/ 214 阅读

相关二维数组中的查找

何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ 题目描述： [http://ac.jobdu.com/problem.php?cid=1039&pid=0][

矫情吗；*/ 2022年03月20日 02:46/ 0 赞/ 236 阅读

相关牛客网在线编程——二维数组中的查找

今天是第二次用牛客的在线编程，上次还是去年的七月一号，已然过去近一年的时间，遇到了不少坑，首先题目看错了，没看到数据是有序的，其次就是对二维数组的输入有些不解，是用户手动输入还

- 日理万妓/ 2022年01月22日 09:19/ 0 赞/ 219 阅读