力扣 搜索二维矩阵
二分查找,闭区间与开区间的不同解法。
题目

乍一看,不是遍历一下找到元素就可以了。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {for (int[] ints : matrix) {for (int ans : ints) {if (ans == target) return true;}}return false;}
}
可以通过的,但还是可以优化一下的。这题可以用二分的思路,可以把整个矩阵看成一大个数组,若将矩阵每一行拼接在上一行的末尾,则会得到一个升序数组,我们可以在该数组上二分找到目标元素。但是这种方法在每一行元素个数不一时会失效。
时间复杂度:O(logmn),空间复杂度:O(1)。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int low = 0, high = m * n - 1;while (low <= high) {int mid = (high - low) / 2 + low;int x = matrix[mid / n][mid % n];if (x < target) {low = mid + 1;} else if (x > target) {high = mid - 1;} else {return true;}}return false;}
}
以上为标准二分查找的写法,其中首尾做为边界,条件时while (low <= high),接着如果目标值偏大则在右边找,即low = mid + 1,反之,目标值偏小时往左边找,即 high = mid - 1,然后当low指针从左边到target时扫了一遍,当high指针从右边到target时扫了一遍,当两个指针重叠相遇时,进一步判断两个指针定住的数是不是目标数,然后退出循环。
这题还可以先对行二分,再对列二分,进行两次二分查找。每行的第一个元素大于前一行的第一个元素,矩阵第一列的元素是升序的。对矩阵的第一列的元素二分查找,找到最后一个不大于目标值的元素,然后在该元素所在行中二分查找目标值是否存在。
时间复杂度:O(logmn),空间复杂度:O(1)。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int rowIndex = binarySearchFirstColumn(matrix, target);if (rowIndex < 0) {return false;}return binarySearchRow(matrix[rowIndex], target);}public int binarySearchFirstColumn(int[][] matrix, int target) {int low = -1, high = matrix.length - 1;while (low < high) {int mid = (high - low + 1) / 2 + low;if (matrix[mid][0] <= target) {low = mid;} else {high = mid - 1;}}return low;}public boolean binarySearchRow(int[] row, int target) {int low = 0, high = row.length - 1;while (low <= high) {int mid = (high - low) / 2 + low;if (row[mid] == target) {return true;} else if (row[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return false;}
}
其中,用了一个左开右闭区间的二分查找,可以先进行扩充边界,然后条件改为while (low < high),接着low要设置为mid,退出的条件即当low跟high重叠时,此时的low是mid了,看是不是要找的target。当然,这题用左闭右开区间的二分查找也是类似,不过要注意以下返回值,要取到不大于目标值的最大行索引。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int rowIndex = binarySearchFirstColumn(matrix, target);if (rowIndex < 0) {return false;}return binarySearchRow(matrix[rowIndex], target);}
public int binarySearchFirstColumn(int[][] matrix, int target) {int low = 0, high = matrix.length; while (low < high) { int mid = (high - low) / 2 + low; if (matrix[mid][0] <= target) { low = mid + 1;} else { high = mid; }}return high-1;
}public boolean binarySearchRow(int[] row, int target) {int low = 0, high = row.length - 1;while (low <= high) {int mid = (high - low) / 2 + low;if (row[mid] == target) {return true;} else if (row[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return false;}
}
然后,也可以用最经典的标准二分模板去写。
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int rowIndex = binarySearchFirstColumn(matrix, target);if (rowIndex < 0) {return false;}return binarySearchRow(matrix[rowIndex], target);}
public int binarySearchFirstColumn(int[][] matrix, int target) {// 初始化low为0,high为矩阵最后一行的索引int low = 0, high = matrix.length - 1;while (low <= high) { // 当low不大于high时继续循环int mid = (high - low) / 2 + low; // 计算中间位置// 如果中间位置的行的第一个元素小于或等于目标值,则该行及之后的行可能是候选行if (matrix[mid][0] <= target) {low = mid + 1; } else {high = mid - 1; }}// 返回不大于目标值的最大行索引return high; // 这里返回high,因为high指向的是不大于目标值的最大行索引或未找到返回-1}public boolean binarySearchRow(int[] row, int target) {int low = 0, high = row.length - 1;while (low <= high) {int mid = (high - low) / 2 + low;if (row[mid] == target) {return true;} else if (row[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return false;}
}
二分查找模板巧记,先写好数组中的左右边界值,然后while (low <= high),接着写mid的求值 int mid = (high - low) / 2 + low,再到判断,若目标值偏大往大的找即low指针右移,若目标值偏小往小的找即high指针左移,最后当low跟high重叠时对当前元素做判断,返回值依题而定。
相关文章:
力扣 搜索二维矩阵
二分查找,闭区间与开区间的不同解法。 题目 乍一看,不是遍历一下找到元素就可以了。 class Solution {public boolean searchMatrix(int[][] matrix, int target) {for (int[] ints : matrix) {for (int ans : ints) {if (ans target) return true;}}…...
JavaScript 操作符与表达式
Hi, 我是布兰妮甜,编写流畅、愉悦用户体验的程序员。JavaScript 是一种功能强大且灵活的编程语言,广泛应用于前端和后端开发。它提供了一系列丰富的操作符和表达式来处理数据、执行逻辑判断以及控制程序流程。理解这些概念对于编写高效、可读性强的代码至…...
深度学习 Pytorch 张量(Tensor)的创建和常用方法
1 张量的基本创建及其类型 和Numpy中的array一样,张量的本质也是结构化地组织了大量的数据。 并且在实际操作中,张量的创建和基本功能也与其非常类似。 1.1 张量(Tensor)函数创建方法 张量的最基本创建方法和Numpy中创建Array的格式一致。 # Numpy创建…...
在VMwareFusion中使用Ubuntu
在VMwareFusion使用Ubuntu 在VMwareFusion使用Ubuntu背景在VMwareFusion虚拟机里使用Ubuntu1、集成桌面工具2、主机和虚拟机之间共享剪贴板内容3、设置root用户密码4、设置静态ip4.1、静态ip和动态ip的区别4.2、查看当前ip4.2、linux网络配置文件所在位置4.3、基于ubuntu22.04.…...
%.*s——C语言中printf 函数中的一种格式化输出方式
在C语言中,%.*s 是 printf 函数中的一种格式化输出方式,用于控制字符串的输出长度。具体来说,%.*s 中的 * 表示输出宽度(即最多输出的字符数)是一个变量,这个变量的值在运行时通过 printf 函数的参数传递。…...
基于微信小程序的摄影竞赛系统设计与实现(LW+源码+讲解)
专注于大学生项目实战开发,讲解,毕业答疑辅导,欢迎高校老师/同行前辈交流合作✌。 技术范围:SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容:…...
hydra破解密码
hydra九头蛇是常用的密码破解工具 1、破解centos ssh密码 hydra -l root -P password.txt ssh://192.168.1.107:2222 hydra -l root -P password.txt -s 2222 192.168.1.107 ssh2、破解ftp hydra -l allen -P e:\aa.txt ftp://127.0.0.1 hydra -l allen -P e:\aa.txt ftp:…...
JAVA之外观模式
外观模式,又称门面模式,是一种结构型设计模式,旨在为复杂的子系统提供一个统一且简化的接口。通过这一模式,客户端可以更加便捷地与子系统交互,而无需深入了解其内部结构和实现细节。外观模式不仅简化了客户端的使用&a…...
如何选择合适的服务器?服务器租赁市场趋势分析
服务器租赁市场概览 服务器租赁 market可以分为两种类型:按小时、按月和按年,每种模式都有其特点和适用场景,按小时租赁是最经济实惠的选择,适用于短期需求;按月租赁则适合中长期使用;而按年租赁则是最灵活…...
CentOS 下载软件时报Error: Failed to synchronize cache for repo ‘AppStream‘解决方法
下载软件时出现以下问题 直接把CentOS-AppStream.repo改个名字就行 cd /etc/yum.repos.d/ mv CentOS-AppStream.repo CentOS-AppStream.repo.bak就可以了 解决思路 把AI问遍,无人会,解决法 想要下载软件通通失败了,解决方法当然是问AI&am…...
鲍厚霖:引领AI广告创新,搭建中美合作桥梁
2024年是鲍厚霖和她领导的超能S咨询公司(Triple S AI)收获颇丰的一年。这一年中,她以卓越的战略眼光和创新能力,为中美教育、文化与技术的深度融合注入了新的活力。2025年,Triple S AI计划推出全新2.0版本平台,进一步深化人工智能驱动的营销与文化合作领域,推动产业变革与社会福…...
学习记录1
[SUCTF 2019]EasyWeb 直接给了源代码,分析一下 <?php function get_the_flag(){// webadmin will remove your upload file every 20 min!!!! $userdir "upload/tmp_".md5($_SERVER[REMOTE_ADDR]);if(!file_exists($userdir)){mkdir($userdir);}if…...
【Gossip 协议】Golang的实现库Memberlist 库简介
Gossip 协议简介 Gossip 协议是一种分布式协议,用于在节点之间传播信息,常用于成员管理、故障检测、服务发现等场景。在这个协议中,每个节点定期与其他节点交换信息,最终保证所有节点达到一致的状态。它的工作原理类似于人群中的…...
LDD3学习7--硬件接口I/O端口(以short为例)
1 理论 1.1 基本概念 目前对外设的操作,都是通过寄存器。寄存器的概念,其实就是接口,访问硬件接口,有I/O端口通信和内存映射I/O (Memory-Mapped I/O),I/O端口通信是比较老的那种,都是老的串口并口设备&am…...
openharmony电源管理子系统
电源管理子系统 简介目录使用说明相关仓 简介 电源管理子系统提供如下功能: 重启服务:系统重启和下电。系统电源管理服务:系统电源状态管理和休眠运行锁管理。显示相关的能耗调节:包括根据环境光调节背光亮度,和根…...
【Rust自学】13.4. 闭包 Pt.4:使用闭包捕获环境
13.4.0. 写在正文之前 Rust语言在设计过程中收到了很多语言的启发,而函数式编程对Rust产生了非常显著的影响。函数式编程通常包括通过将函数作为值传递给参数、从其他函数返回它们、将它们分配给变量以供以后执行等等。 在本章中,我们会讨论 Rust 的一…...
在 macOS 上,用命令行连接 MySQL(/usr/local/mysql/bin/mysql -u root -p)
根据你提供的文件内容,MySQL 的安装路径是 /usr/local/mysql。要直接使用 mysql 命令,你需要找到 mysql 可执行文件的路径。 在 macOS 上,mysql 客户端通常位于 MySQL 安装目录的 bin 子目录中。因此,完整的路径应该是࿱…...
mono3d汇总
lidar坐标系 lidar坐标系可以简单归纳为标准lidar坐标系和nucense lidar坐标系,参考链接。这个坐标系和车辆的ego坐标系是一致的。 标准lidar坐标系 opendet3d,mmdetection3d和kitt都i使用了该坐标系 up z^ x front| /| /left y <------ 0kitti采…...
K8S 节点选择器
今天我们来实验 pod 调度的 nodeName 与 nodeSelector。官网描述如下: 假设有如下三个节点的 K8S 集群: k8s31master 是控制节点 k8s31node1、k8s31node2 是工作节点 容器运行时是 containerd 一、镜像准备 1.1、镜像拉取 docker pull tomcat:8.5-jre8…...
【2024年华为OD机试】 (C卷,200分)- 反射计数(Java JS PythonC/C++)
一、问题描述 题目解析 题目描述 给定一个包含 0 和 1 的二维矩阵,一个物体从给定的初始位置出发,在给定的速度下进行移动。遇到矩阵的边缘时会发生镜面反射。无论物体经过 0 还是 1,都不影响其速度。请计算并给出经过 t 时间单位后&#…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
