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

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. 搜索二维矩阵

目录 题目描述解法方法一&#xff1a;二分查找方法二&#xff1a;从左下角或右上角搜索 运行结果方法一方法二 题目描述 给你一个满足下述两条属性的 m x n 整数矩阵&#xff1a; 每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给…...

如何安全地添加液氮到液氮罐中

液氮是一种极低温的液体&#xff0c;它在许多领域广泛应用&#xff0c;但在处理液氮时需谨慎小心。添加液氮到液氮罐中是一个常见的操作&#xff0c;需要遵循一些安全准则以确保操作人员的安全和设备的完整性。 选择合适的液氮容器 选用专业设计用于存储液氮的容器至关重要。…...

LGBM算法 原理

简介 GBDT (Gradient Boosting Decision Tree) 是机器学习中一个长盛不衰的模型&#xff0c;其主要思想是利用弱分类器&#xff08;决策树&#xff09;迭代训练以得到最优模型&#xff0c;该模型具有训练效果好、不易过拟合等优点。GBDT不仅在工业界应用广泛&#xff0c;通常被…...

【WPF应用5】WPF中的TextBlock控件:属性与事件详解及示例

在WPF&#xff08;Windows Presentation Foundation&#xff09;开发中&#xff0c;TextBlock控件是一个常用的元素&#xff0c;用于显示静态或动态文本内容。它提供了丰富的属性和事件&#xff0c;使得开发者能够灵活地控制文本的显示样式和响应用户的交互行为。本文将详细介绍…...

【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的网络聊天室 项目需求&#xff1a; 如果有用户登录&#xff0c;其他用户可以收到这个人的登录信息如果有人发送信息&#xff0c;其他用户可以收到这个人的群聊信息如果有人下线&#xff0c;其他用户可以收到这个人的下线信息服务器可以发送系统信息 服务器端代码 #in…...

Excel双击单元格后弹窗输入日期

Step1. 在VBE界面新建一个窗体(Userform1),在窗体的工具箱的空白处右键,选中添加附件,勾选Calendar control 8.0,即可完成日历的添加。 PS:遗憾的是, Office 64 位没有官方的日期选择器控件。唯一的解决方案是使用Excel 的第三方日历。 参考链接:How to insert calen…...

原生 HTML/CSS/JS 实现右键菜单和二级菜单

文章来源&#xff1a;www.huhailong.vip 站点 文章源地址&#xff1a;https://www.huhailong.vip/article/1764653112011841538 Demo效果演示地址 先看效果图 {{{width“auto” height“auto”}}} 需要注意的就是边界检测处理&#xff0c;到极端点击底部和右侧时如果不做处理会…...

[项目前置]如何用webbench进行压力测试

测试软件 采用webbench进行服务器性能测试。 Webbench是知名的网站压力测试工具&#xff0c;它是由Lionbridge公司开发。 webbench的标准测试可以向我们展示服务器的两项内容&#xff1a; 每秒钟相应请求数 和 每秒钟传输数据量 webbench测试原理是&#xff0c;创建指定数…...

网络七层模型:理解网络通信的架构(〇)

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《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安全数据摆渡系统 构建便捷的内外网数据交换通道

安全数据摆渡系统是一种设计用于解决内外网环境下&#xff0c;数据传输、管理、共享问题的安全系统&#xff0c;通过加密、访问控制等策略&#xff0c;提供安全可靠的数据传输和共享服务&#xff0c;尤其适用于对网络安全建设要求高的行业&#xff0c;比如研发型企业、党政机构…...

【云开发笔记No.14】持续交付、持续部署、持续交付流水线

一、持续交付 持续交付&#xff08;Continuous Delivery&#xff09;是一种软件开发方法论&#xff0c;它强调在开发过程中&#xff0c;软件可以在任何时间以最小的努力被部署到生产环境。其核心是确保代码更改在经过一系列自动化测试后&#xff0c;能够快速、安全地集成到主代…...

蓝桥杯练习07小兔子爬楼梯

小兔子爬楼梯 介绍 小兔子想去月球上旅行&#xff0c;假设小兔子拥有一个阶梯子&#xff0c;当你爬完层就可以到达月球&#xff0c;小兔子每次可以跳1或者2个台阶&#xff0c;小兔子有多少种跳法可以到达月球呢&#xff1f; 给定n是一个正整数&#xff0c;代表梯子的阶数&…...

Docker in Docker原理与实战

Docker in Docker (DinD) 是一种在Docker容器内部运行Docker的技术。它允许在一个Docker容器内部创建和管理其他的Docker容器&#xff0c;实现了一个容器内部的容器编排环境。本文将介绍Docker in Docker的原理&#xff0c;并给出一个实际的应用场景。 Docker in Docker的原理…...

Ruoyi若依框架下载流程详细解读(SpringBoot-Vue)

图解&#xff1a; 前端设计&#xff1a; 前端设计一个link文字连接或者按钮&#xff08;ElementUI&#xff09;Element - The worlds most popular Vue UI framework 前端请求设计&#xff1a; import request from /utils/request //下载示例模型定义语言的JSON export const…...

【深度学习】Pytorch中实现交叉熵损失计算的方式总结

在PyTorch中&#xff0c;计算交叉熵损失主要有以下几种方式&#xff0c;它们针对不同的场景和需求有不同的实现方式和适用范围&#xff1a; 1. nn.CrossEntropyLoss 类 这是最常用且方便的方法&#xff0c;特别适用于多分类任务。nn.CrossEntropyLoss 实际上是同时完成了 sof…...

机器学习:处理jira工单的分类问题

如何根据jira工单的category、reporter自动找到处理它的组呢?这是一个利用机器学习中knn算法的小实践. 目录 Knn算法 数据 示例 分割数据 选择Neighbors knn的优缺点 机器学习是一种技术,它的目的是给机器学习能力,让它们可以根据数据自己做决定,所以对于训练…...

后端常问面经之操作系统

请简要描述线程与进程的关系,区别及优缺点&#xff1f; 本质区别&#xff1a;进程是操作系统资源分配的基本单位&#xff0c;而线程是任务调度和执行的基本单位 在开销方面&#xff1a;每个进程都有独立的代码和数据空间&#xff08;程序上下文&#xff09;&#xff0c;程序之…...

RK3568平台 iperf3测试网络性能

一.iperf3简介 iperf是一款开源的网络性能测试工具&#xff0c;主要用于测量TCP和UDP带宽性能。它可以在不同的操作系统上运行&#xff0c;包括Windows、Linux、macOS等。iperf具有简单易用、功能强大、高度可配置等特点&#xff0c;广泛应用于网络性能测试、网络故障诊断和网…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

C++实现分布式网络通信框架RPC(2)——rpc发布端

有了上篇文章的项目的基本知识的了解&#xff0c;现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...

数据分析六部曲?

引言 上一章我们说到了数据分析六部曲&#xff0c;何谓六部曲呢&#xff1f; 其实啊&#xff0c;数据分析没那么难&#xff0c;只要掌握了下面这六个步骤&#xff0c;也就是数据分析六部曲&#xff0c;就算你是个啥都不懂的小白&#xff0c;也能慢慢上手做数据分析啦。 第一…...