首页 > 编程语言 >剑指offer04(Java)二维数组中的查找(中等)

剑指offer04(Java)二维数组中的查找(中等)

时间:2023-03-27 12:23:50浏览次数:78  
标签:Java matrix int offer04 length 查找 return false target

题目:

在一个 n * m 的二维数组中,每一行都按照从左到右 非递减 的顺序排序,每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下:

限制:

0 <= n <= 1000

0 <= m <= 1000

本题与:力扣240(java&python)-搜索二维矩阵 II(中等)相同

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

方法一:暴力求解,直接遍历二维数组中的每个元素,并与target相比较。

 1 class Solution {
 2     public boolean findNumberIn2DArray(int[][] matrix, int target) {
 3          //判空
 4         if (matrix.length == 0 || matrix[0].length == 0) return false;
 5         int n = matrix.length;
 6         int m = matrix[0].length;
 7         //直接遍历每个元素
 8         for (int[] rows : matrix){
 9             //遍历每一行中的每个元素
10             for (int num : rows){
11                 if (num == target) return true;
12             }
13         }
14         return false;
15     }
16 }

方法二:坐标轴法:参考k神的题解,每次排除一行

在当前索引不越界的情况下:从矩阵 matrix 左下角元素(索引设为 (i, j) )开始遍历,并与目标值对比:

①当 matrix[i][j] > target 时,那么[i,j]右边的所有元素都大于目标值,执行 i-- ,即消去第 i 行后面的所有元素;
②当 matrix[i][j] < target 时,那么[i,j]上面的所有元素都小于目标值,执行 j++ ,即消去第 j 列上面的所有元素;
③当 matrix[i][j] = target 时,返回true。

当行索引或列索引越界时,则代表矩阵中无目标值,返回 false 。

 1 class Solution {
 2     public boolean findNumberIn2DArray(int[][] matrix, int target) {
 3          //判空
 4         if (matrix.length == 0 || matrix[0].length == 0) return false;
 5         //n:行;m:列
 6         int n = matrix.length, m = matrix[0].length;
 7         int i = n - 1, j = 0;
 8         while (i >= 0 && j < m){
 9             if (matrix[i][j] > target){
10                 i--;
11             }else if (matrix[i][j] < target){
12                 j++;
13             }else {
14                 return true;
15             }
16         }
17         return false;
18     }
19 }

标签:Java,matrix,int,offer04,length,查找,return,false,target
From: https://www.cnblogs.com/liu-myu/p/17261133.html

相关文章

  • Java静态代理和动态代理的区别
    一、静态代理代理模式可以在不修改被代理对象的基础上,通过扩展代理类,进行一些功能的附加与增强。代理类和被代理类应该共同实现一个接口,或者是共同继承某个类。优点:可以在......
  • 【JavaScript快速排序算法】不同版本原理分析
    说明快速排序(QuickSort),又称分区交换排序(partition-exchangesort),简称快排。快排是一种通过基准划分区块,再不断交换左右项的排序方式,其采用了分治法,减少了交换的次数。它的......
  • 某大厂面试题:说一说Java、Spring、Dubbo三者SPI机制的原理和区别
    大家好,我是三友~~今天来跟大家聊一聊Java、Spring、Dubbo三者SPI机制的原理和区别。其实我之前写过一篇类似的文章,但是这篇文章主要是剖析dubbo的SPI机制的源码,中间只是......
  • Java 在代码中区分json和array
    publicstaticvoidmain(String[]args){Stringn="{\n"+""data":[\n"+"{\n"+""category":"设计资质",\n"+""certNameL......
  • java List报错Method threw ‘java.lang.UnsupportedOperationException‘ exception.
    List<String>status=Arrays.asList(query.getStatus().name());if(query.getStatusMap()==1){if(query.getStatus().equals(FileStatus.EXTRACTING)){......
  • 常见java面试题以及对代码的理解
    1、Students=newStudent();做了哪些事情A:加载Student.class文件进内存B:在栈中为s开辟空间C:在堆中为学生对象开辟空间D:为学生对象的成员变量赋默认值......
  • 为什么不建议使用Java序列化?
    把对象转换为字节序列的过程称为对象的序列化。什么情况下需要用到序列化:把的内存中的对象状态保存到一个文件中或者数据库中时候;使用套接字在网络上传送对象的时......
  • Kotlin 与 JAVA 不同之处
    添加kotlin混编支持要在Android项目中添加Kotlin混编支持,需要进行以下步骤:在项目的build.gradle文件中添加以下代码:kotlinandroid{...//添加kotlin支......
  • Java学习日记
    2023.3.26学习Java打卡类型转换不同类型数据先转化为同一类型,再运算:#低--------------------→高byte,short,char-→int-→long-→float-→double例如://强制转换......
  • 用java实现书城项目(简单增删改查2)
    书城项目登录dao接口:UserDaoUserslogin(Stringusername,Stringpassword);实现:UserDaoImplQueryRunnerqueryrunner=newQueryRunner();Connectionconnection......