当前位置: 首页 > 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;广泛应用于网络性能测试、网络故障诊断和网…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...