LeetCode Python - 74. 搜索二维矩阵
目录
- 题目描述
- 解法
- 方法一:二分查找
- 方法二:从左下角或右上角搜索
- 运行结果
- 方法一
- 方法二
题目描述
给你一个满足下述两条属性的 m x n 整数矩阵:
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。
示例 1:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true
示例 2:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false
提示:
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 100
- -104 <= matrix[i][j], target <= 104
解法
方法一:二分查找
我们将二维矩阵逻辑展开,然后二分查找即可。
时间复杂度 O(log(m×n))。其中 m 和 n 分别是矩阵的行数和列数。空间复杂度 O(1)。
class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""m, n = len(matrix), len(matrix[0])left, right = 0, m * n - 1while left < right:mid = (left + right) >> 1x, y = divmod(mid, n)if matrix[x][y] >= target:right = midelse:left = mid + 1return matrix[left // n][left % n] == target
方法二:从左下角或右上角搜索
这里我们以左下角作为起始搜索点,往右上方向开始搜索,比较当前元素 matrix[i][j] 与 target 的大小关系:
- 若 matrix[i][j]=target,说明找到了目标值,直接返回 true。
- 若 matrix[i][j]>target,说明这一行从当前位置开始往右的所有元素均大于 target,应该让 i 指针往上移动,即
i=i−1。 - 若 matrix[i][j]<target,说明这一列从当前位置开始往上的所有元素均小于 target,应该让 j 指针往右移动,即
j=j+1。
若搜索结束依然找不到 target,返回 false。
时间复杂度 O(m+n)。其中 m 和 n 分别是矩阵的行数和列数。空间复杂度 O(1)。
class Solution(object):def searchMatrix(self, matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""m, n = len(matrix), len(matrix[0])i, j = m - 1, 0while i >= 0 and j < n:if matrix[i][j] == target:return Trueif matrix[i][j] > target:i -= 1else:j += 1return False
运行结果
方法一

方法二

相关文章:
LeetCode Python - 74. 搜索二维矩阵
目录 题目描述解法方法一:二分查找方法二:从左下角或右上角搜索 运行结果方法一方法二 题目描述 给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给…...
如何安全地添加液氮到液氮罐中
液氮是一种极低温的液体,它在许多领域广泛应用,但在处理液氮时需谨慎小心。添加液氮到液氮罐中是一个常见的操作,需要遵循一些安全准则以确保操作人员的安全和设备的完整性。 选择合适的液氮容器 选用专业设计用于存储液氮的容器至关重要。…...
LGBM算法 原理
简介 GBDT (Gradient Boosting Decision Tree) 是机器学习中一个长盛不衰的模型,其主要思想是利用弱分类器(决策树)迭代训练以得到最优模型,该模型具有训练效果好、不易过拟合等优点。GBDT不仅在工业界应用广泛,通常被…...
【WPF应用5】WPF中的TextBlock控件:属性与事件详解及示例
在WPF(Windows Presentation Foundation)开发中,TextBlock控件是一个常用的元素,用于显示静态或动态文本内容。它提供了丰富的属性和事件,使得开发者能够灵活地控制文本的显示样式和响应用户的交互行为。本文将详细介绍…...
【C语言基础】:内存操作函数
文章目录 一、memcpy函数的使用和模拟实现1.1 memcpy函数的使用1.2 memcpy函数的模拟实现 二、memmove函数的使用和模拟实现2.1 memmove函数的使用2.2 memmove函数的模拟实现 三、memset函数的使用3.1 menset函数的使用 四、memcmp函数的使用4.1 memcmp函数的使用 学海无涯苦作…...
3.24作业
基于UDP的网络聊天室 项目需求: 如果有用户登录,其他用户可以收到这个人的登录信息如果有人发送信息,其他用户可以收到这个人的群聊信息如果有人下线,其他用户可以收到这个人的下线信息服务器可以发送系统信息 服务器端代码 #in…...
Excel双击单元格后弹窗输入日期
Step1. 在VBE界面新建一个窗体(Userform1),在窗体的工具箱的空白处右键,选中添加附件,勾选Calendar control 8.0,即可完成日历的添加。 PS:遗憾的是, Office 64 位没有官方的日期选择器控件。唯一的解决方案是使用Excel 的第三方日历。 参考链接:How to insert calen…...
原生 HTML/CSS/JS 实现右键菜单和二级菜单
文章来源:www.huhailong.vip 站点 文章源地址:https://www.huhailong.vip/article/1764653112011841538 Demo效果演示地址 先看效果图 {{{width“auto” height“auto”}}} 需要注意的就是边界检测处理,到极端点击底部和右侧时如果不做处理会…...
[项目前置]如何用webbench进行压力测试
测试软件 采用webbench进行服务器性能测试。 Webbench是知名的网站压力测试工具,它是由Lionbridge公司开发。 webbench的标准测试可以向我们展示服务器的两项内容: 每秒钟相应请求数 和 每秒钟传输数据量 webbench测试原理是,创建指定数…...
网络七层模型:理解网络通信的架构(〇)
🤍 前端开发工程师、技术日更博主、已过CET6 🍨 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 🕠 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 🍚 蓝桥云课签约作者、上架课程《Vue.js 和 E…...
format(C++20)
1. std::format format_01.cpp // g format_01.cpp -stdc20 #include <iostream> #include <string> #include <format>void test_01() {// 使用字符串填充std::cout << std::format("Hello {}!\n", "World"); // Hello World!…...
Ftrans安全数据摆渡系统 构建便捷的内外网数据交换通道
安全数据摆渡系统是一种设计用于解决内外网环境下,数据传输、管理、共享问题的安全系统,通过加密、访问控制等策略,提供安全可靠的数据传输和共享服务,尤其适用于对网络安全建设要求高的行业,比如研发型企业、党政机构…...
【云开发笔记No.14】持续交付、持续部署、持续交付流水线
一、持续交付 持续交付(Continuous Delivery)是一种软件开发方法论,它强调在开发过程中,软件可以在任何时间以最小的努力被部署到生产环境。其核心是确保代码更改在经过一系列自动化测试后,能够快速、安全地集成到主代…...
蓝桥杯练习07小兔子爬楼梯
小兔子爬楼梯 介绍 小兔子想去月球上旅行,假设小兔子拥有一个阶梯子,当你爬完层就可以到达月球,小兔子每次可以跳1或者2个台阶,小兔子有多少种跳法可以到达月球呢? 给定n是一个正整数,代表梯子的阶数&…...
Docker in Docker原理与实战
Docker in Docker (DinD) 是一种在Docker容器内部运行Docker的技术。它允许在一个Docker容器内部创建和管理其他的Docker容器,实现了一个容器内部的容器编排环境。本文将介绍Docker in Docker的原理,并给出一个实际的应用场景。 Docker in Docker的原理…...
Ruoyi若依框架下载流程详细解读(SpringBoot-Vue)
图解: 前端设计: 前端设计一个link文字连接或者按钮(ElementUI)Element - The worlds most popular Vue UI framework 前端请求设计: import request from /utils/request //下载示例模型定义语言的JSON export const…...
【深度学习】Pytorch中实现交叉熵损失计算的方式总结
在PyTorch中,计算交叉熵损失主要有以下几种方式,它们针对不同的场景和需求有不同的实现方式和适用范围: 1. nn.CrossEntropyLoss 类 这是最常用且方便的方法,特别适用于多分类任务。nn.CrossEntropyLoss 实际上是同时完成了 sof…...
机器学习:处理jira工单的分类问题
如何根据jira工单的category、reporter自动找到处理它的组呢?这是一个利用机器学习中knn算法的小实践. 目录 Knn算法 数据 示例 分割数据 选择Neighbors knn的优缺点 机器学习是一种技术,它的目的是给机器学习能力,让它们可以根据数据自己做决定,所以对于训练…...
后端常问面经之操作系统
请简要描述线程与进程的关系,区别及优缺点? 本质区别:进程是操作系统资源分配的基本单位,而线程是任务调度和执行的基本单位 在开销方面:每个进程都有独立的代码和数据空间(程序上下文),程序之…...
RK3568平台 iperf3测试网络性能
一.iperf3简介 iperf是一款开源的网络性能测试工具,主要用于测量TCP和UDP带宽性能。它可以在不同的操作系统上运行,包括Windows、Linux、macOS等。iperf具有简单易用、功能强大、高度可配置等特点,广泛应用于网络性能测试、网络故障诊断和网…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
【7色560页】职场可视化逻辑图高级数据分析PPT模版
7种色调职场工作汇报PPT,橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版:职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
