当前位置: 首页 > news >正文

力扣 搜索二维矩阵

二分查找,闭区间与开区间的不同解法。

题目

乍一看,不是遍历一下找到元素就可以了。

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重叠时对当前元素做判断,返回值依题而定。

相关文章:

力扣 搜索二维矩阵

二分查找&#xff0c;闭区间与开区间的不同解法。 题目 乍一看&#xff0c;不是遍历一下找到元素就可以了。 class Solution {public boolean searchMatrix(int[][] matrix, int target) {for (int[] ints : matrix) {for (int ans : ints) {if (ans target) return true;}}…...

JavaScript 操作符与表达式

Hi, 我是布兰妮甜&#xff0c;编写流畅、愉悦用户体验的程序员。JavaScript 是一种功能强大且灵活的编程语言&#xff0c;广泛应用于前端和后端开发。它提供了一系列丰富的操作符和表达式来处理数据、执行逻辑判断以及控制程序流程。理解这些概念对于编写高效、可读性强的代码至…...

深度学习 Pytorch 张量(Tensor)的创建和常用方法

1 张量的基本创建及其类型 和Numpy中的array一样&#xff0c;张量的本质也是结构化地组织了大量的数据。 并且在实际操作中&#xff0c;张量的创建和基本功能也与其非常类似。 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语言中&#xff0c;%.*s 是 printf 函数中的一种格式化输出方式&#xff0c;用于控制字符串的输出长度。具体来说&#xff0c;%.*s 中的 * 表示输出宽度&#xff08;即最多输出的字符数&#xff09;是一个变量&#xff0c;这个变量的值在运行时通过 printf 函数的参数传递。…...

基于微信小程序的摄影竞赛系统设计与实现(LW+源码+讲解)

专注于大学生项目实战开发,讲解,毕业答疑辅导&#xff0c;欢迎高校老师/同行前辈交流合作✌。 技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;…...

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之外观模式

外观模式&#xff0c;又称门面模式&#xff0c;是一种结构型设计模式&#xff0c;旨在为复杂的子系统提供一个统一且简化的接口。通过这一模式&#xff0c;客户端可以更加便捷地与子系统交互&#xff0c;而无需深入了解其内部结构和实现细节。外观模式不仅简化了客户端的使用&a…...

如何选择合适的服务器?服务器租赁市场趋势分析

服务器租赁市场概览 服务器租赁 market可以分为两种类型&#xff1a;按小时、按月和按年&#xff0c;每种模式都有其特点和适用场景&#xff0c;按小时租赁是最经济实惠的选择&#xff0c;适用于短期需求&#xff1b;按月租赁则适合中长期使用&#xff1b;而按年租赁则是最灵活…...

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问遍&#xff0c;无人会&#xff0c;解决法 想要下载软件通通失败了&#xff0c;解决方法当然是问AI&am…...

鲍厚霖:引领AI广告创新,搭建中美合作桥梁

2024年是鲍厚霖和她领导的超能S咨询公司(Triple S AI)收获颇丰的一年。这一年中,她以卓越的战略眼光和创新能力,为中美教育、文化与技术的深度融合注入了新的活力。2025年,Triple S AI计划推出全新2.0版本平台,进一步深化人工智能驱动的营销与文化合作领域,推动产业变革与社会福…...

学习记录1

[SUCTF 2019]EasyWeb 直接给了源代码&#xff0c;分析一下 <?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 协议是一种分布式协议&#xff0c;用于在节点之间传播信息&#xff0c;常用于成员管理、故障检测、服务发现等场景。在这个协议中&#xff0c;每个节点定期与其他节点交换信息&#xff0c;最终保证所有节点达到一致的状态。它的工作原理类似于人群中的…...

LDD3学习7--硬件接口I/O端口(以short为例)

1 理论 1.1 基本概念 目前对外设的操作&#xff0c;都是通过寄存器。寄存器的概念&#xff0c;其实就是接口&#xff0c;访问硬件接口&#xff0c;有I/O端口通信和内存映射I/O (Memory-Mapped I/O)&#xff0c;I/O端口通信是比较老的那种&#xff0c;都是老的串口并口设备&am…...

openharmony电源管理子系统

电源管理子系统 简介目录使用说明相关仓 简介 电源管理子系统提供如下功能&#xff1a; 重启服务&#xff1a;系统重启和下电。系统电源管理服务&#xff1a;系统电源状态管理和休眠运行锁管理。显示相关的能耗调节&#xff1a;包括根据环境光调节背光亮度&#xff0c;和根…...

【Rust自学】13.4. 闭包 Pt.4:使用闭包捕获环境

13.4.0. 写在正文之前 Rust语言在设计过程中收到了很多语言的启发&#xff0c;而函数式编程对Rust产生了非常显著的影响。函数式编程通常包括通过将函数作为值传递给参数、从其他函数返回它们、将它们分配给变量以供以后执行等等。 在本章中&#xff0c;我们会讨论 Rust 的一…...

在 macOS 上,用命令行连接 MySQL(/usr/local/mysql/bin/mysql -u root -p)

根据你提供的文件内容&#xff0c;MySQL 的安装路径是 /usr/local/mysql。要直接使用 mysql 命令&#xff0c;你需要找到 mysql 可执行文件的路径。 在 macOS 上&#xff0c;mysql 客户端通常位于 MySQL 安装目录的 bin 子目录中。因此&#xff0c;完整的路径应该是&#xff1…...

mono3d汇总

lidar坐标系 lidar坐标系可以简单归纳为标准lidar坐标系和nucense lidar坐标系&#xff0c;参考链接。这个坐标系和车辆的ego坐标系是一致的。 标准lidar坐标系 opendet3d&#xff0c;mmdetection3d和kitt都i使用了该坐标系 up z^ x front| /| /left y <------ 0kitti采…...

K8S 节点选择器

今天我们来实验 pod 调度的 nodeName 与 nodeSelector。官网描述如下&#xff1a; 假设有如下三个节点的 K8S 集群&#xff1a; k8s31master 是控制节点 k8s31node1、k8s31node2 是工作节点 容器运行时是 containerd 一、镜像准备 1.1、镜像拉取 docker pull tomcat:8.5-jre8…...

【2024年华为OD机试】 (C卷,200分)- 反射计数(Java JS PythonC/C++)

一、问题描述 题目解析 题目描述 给定一个包含 0 和 1 的二维矩阵&#xff0c;一个物体从给定的初始位置出发&#xff0c;在给定的速度下进行移动。遇到矩阵的边缘时会发生镜面反射。无论物体经过 0 还是 1&#xff0c;都不影响其速度。请计算并给出经过 t 时间单位后&#…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...