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

Python算法题集_搜索二维矩阵

Python算法题集_搜索二维矩阵

  • 题74:搜索二维矩阵
  • 1. 示例说明
  • 2. 题目解析
    • - 题意分解
    • - 优化思路
    • - 测量工具
  • 3. 代码展开
    • 1) 标准求解【矩阵展开为列表+二分法】
    • 2) 改进版一【行*列区间二分法】
    • 3) 改进版二【第三方模块】
  • 4. 最优算法
  • 5. 相关资源

本文为Python算法题集之一的代码示例

题74:搜索二维矩阵

1. 示例说明

  • 给你一个满足下述两条属性的 m x n 整数矩阵:

    • 每行中的整数从左到右按非严格递增顺序排列。
    • 每行的第一个整数大于前一行的最后一个整数。

    给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false

    示例 1:

    img

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

    示例 2:

    img

    输入: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

2. 题目解析

- 题意分解

  1. 本题是在已排序二维矩阵中查找目标数字
  2. 最快方式就是二分法

- 优化思路

  1. 通常优化:减少循环层次

  2. 通常优化:增加分支,减少计算集

  3. 通常优化:采用内置算法来提升计算速度

  4. 分析题目特点,分析最优解

    1. 本题的已排序二维矩阵可以连成排序一维列表,实现一维列表二分法

    2. 本题的二维矩阵首尾可以连成排序一维列表,定位具体行之后,在具体行中再进行二分查找

    3. 可以考虑使用排序列表操作模块bisect

- 测量工具

  • 本地化测试说明:LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】,因此需要本地化测试解决数据波动问题
  • CheckFuncPerf(本地化函数用时和内存占用测试模块)已上传到CSDN,地址:Python算法题集_检测函数用时和内存占用的模块
  • 本题本地化超时测试用例自己生成,详见章节【最优算法】,代码文件包含在【相关资源】中

3. 代码展开

1) 标准求解【矩阵展开为列表+二分法】

将矩阵展开为列表,再通过二分法查找目标数值是否存在

页面功能测试,马马虎虎,超过53%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def searchMatrix_base(self, matrix, target):if not matrix:return Falseimaxrow, imaxcol, listval = len(matrix), len(matrix[0]), []for iIdx in range(len(matrix)):listval.extend(matrix[iIdx])ileft, iright = 0, len(listval) - 1while ileft <= iright:imid = (iright - ileft) // 2 + ileftif target == listval[imid]:return Trueif target < listval[imid]:iright = imid - 1else:ileft = imid + 1return FalseaSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.searchMatrix_base, mapnums, itarget)
print(result['msg'], '执行结果 = {}'.format(result['result']))# 运行结果
函数 searchMatrix_base 的运行时间为 12768.90 ms;内存使用量为 467828.00 KB 执行结果 = True

2) 改进版一【行*列区间二分法】

将下标换算为行*最大列数+列,将矩阵换算为0 -> 行 * 列的线性区间,在这个区间通过二分法查找目标数值是否存在

页面功能测试,马马虎虎,超过33%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def searchMatrix_ext1(self, matrix, target):if not matrix:return Falseimaxrow, imaxcol = len(matrix), len(matrix[0])ileft, iright = 0, imaxrow * imaxcol - 1while ileft <= iright:imid = (ileft + iright) // 2mid_row, mid_col = imid // imaxcol, imid % imaxcolif matrix[mid_row][mid_col] == target:return Trueelif matrix[mid_row][mid_col] < target:ileft = imid + 1elif matrix[mid_row][mid_col] > target:iright = imid - 1return FalseaSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.searchMatrix_ext1, mapnums, itarget)
print(result['msg'], '执行结果 = {}'.format(result['result']))# 运行结果
函数 searchMatrix_ext1 的运行时间为 0.00 ms;内存使用量为 12.00 KB 执行结果 = True

3) 改进版二【第三方模块】

将矩阵展开为列表,再使用排序列表操作模块bisect来查找插入位置

页面功能测试,性能一般,超过82%在这里插入图片描述

import CheckFuncPerf as cfpclass Solution:def searchMatrix_ext2(self, matrix, target):if not matrix:return Falseimaxrow, imaxcol, listval = len(matrix), len(matrix[0]), []for iIdx in range(len(matrix)):listval.extend(matrix[iIdx])from bisect import bisect_leftipos = bisect_left(listval, target)if ipos == imaxrow * imaxcol:return Falsereturn listval[ipos] == targetaSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.searchMatrix_ext2, mapnums, itarget)
print(result['msg'], '执行结果 = {}'.format(result['result']))# 运行结果
函数 searchMatrix_ext2 的运行时间为 0.00 ms;内存使用量为 12.00 KB 执行结果 = True

4. 最优算法

根据本地日志分析,最优算法为第2种方式【行*列区间二分法】searchMatrix_ext1

本题测试数据,似乎能推出以下结论:

  1. 二分法查询性能非常夸张,简直是瞬间定位【1亿的数组,1毫秒定位】
  2. 数据的迁移【从矩阵->列表】耗时耗内存,这也是大数据兴起的原因之一【数据的迁移代价远高于计算代价】
  3. 第三方模块的函数消耗内存非常小
import random
imaxrow, imaxcol, istart = 10000, 10000, 0
mapnums = [[0 for x in range(imaxcol)] for y in range(imaxrow)]
for irow in range(imaxrow):for icol in range(imaxcol):istart += random.randint(0, 6)mapnums[irow][icol] = istart
itarget = mapnums[imaxrow//2][imaxcol//2]
aSolution = Solution()
result = cfp.getTimeMemoryStr(aSolution.searchMatrix_base, mapnums, itarget)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(aSolution.searchMatrix_ext1, mapnums, itarget)
print(result['msg'], '执行结果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(aSolution.searchMatrix_ext2, mapnums, itarget)
print(result['msg'], '执行结果 = {}'.format(result['result']))# 算法本地速度实测比较
函数 searchMatrix_base 的运行时间为 12768.90 ms;内存使用量为 467828.00 KB 执行结果 = True
函数 searchMatrix_ext1 的运行时间为 0.00 ms;内存使用量为 12.00 KB 执行结果 = True
函数 searchMatrix_ext2 的运行时间为 6336.15 ms;内存使用量为 1508.00 KB 执行结果 = True

5. 相关资源

本文代码已上传到CSDN,地址:Python算法题源代码_LeetCode(力扣)_搜索二维矩阵

一日练,一日功,一日不练十日空

may the odds be ever in your favor ~

相关文章:

Python算法题集_搜索二维矩阵

Python算法题集_搜索二维矩阵 题74&#xff1a;搜索二维矩阵1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【矩阵展开为列表二分法】2) 改进版一【行*列区间二分法】3) 改进版二【第三方模块】 4. 最优算法5. 相关资源 本文为Python算法题集之…...

学习笔记:顺序表和链表(一、顺序表)

首先来个导言&#xff1a; 1.数组的优势&#xff1a;下标的随机访问&#xff0c;物理空间连续。数组指针用[ ]或者 * , 结构体指针用 - > 2.书写习惯 test.c写出主体框架 QelList.c写出结构体、头文件、函数声明 QelList.c写出函数的实现 3.挪动&#xff1a;如果从前…...

Midjourney从入门到实战:图像生成命令及参数详解

目录 0 专栏介绍1 Midjourney Bot常用命令2 Midjourney绘图指令格式3 Midjourney绘图指令参数3.1 模型及版本3.2 画面比例3.3 风格化3.4 图片质量3.5 混乱值3.6 随机数种子3.7 重复贴图3.8 停止3.8 垫图权重3.9 提示词权重分割 0 专栏介绍 &#x1f525;Midjourney是目前主流的…...

C语言分析基础排序算法——插入排序

目录 插入排序 直接插入排序 希尔排序 希尔排序基本思路解析 希尔排序优化思路解析 完整希尔排序文件 插入排序 直接插入排序 所谓直接插入排序&#xff0c;即每插入一个数据和之前的数据进行大小比较&#xff0c;如果较大放置在后面&#xff0c;较小放置在前面&#x…...

海格里斯HEGERLS智能托盘四向车系统为物流仓储自动化升级提供新答案

随着实体企业面临需求多样化、订单履行实时化、商业模式加速迭代等挑战&#xff0c;客户对物流仓储解决方案的需求也逐渐趋向于柔性化、智能化。作为近十年来发展起来的新型智能仓储设备&#xff0c;四向车系统正是弥补了先前托盘搬运领域柔性解决方案的空白。随着小车本体设计…...

SQLiteC/C++接口详细介绍-sqlite3类(一)

上一篇&#xff1a;SQLiteC/C接口简介 下一篇&#xff1a;SQLiteC/C接口详细介绍&#xff08;二&#xff09; 引言&#xff1a; SQLite C/C 数据库接口是一个流行的SQLite库使用形式&#xff0c;它允许开发者在C和C代码中嵌入 SQLite 基本功能的解决方案。通过 SQLite C/C 数据…...

基于UDP实现直播间聊天的功能

需求&#xff1a;软件划分为用户客户端和主播服务端两个软件client.c和server.c 用户客户端负责&#xff1a;1.接收用户的昵称2.接收用户输入的信息&#xff0c;能够将信息发送给服务端3.接收服务端回复的数据信息,并完成显示主播服务端负责&#xff1a;1.对所有加入直播间的用…...

html5cssjs代码 006 文章排版《桃花源记》

html5&css&js代码 006 文章排版《桃花源记》 一、代码二、解释页面整体结构&#xff1a;头部信息&#xff1a;CSS样式&#xff1a;文章内容&#xff1a; 这段代码定义了一个网页&#xff0c;用于展示文章《桃花源记》的内容。网页使用了CSS样式来定义各个部分的显示效果…...

勾八头歌之数据科学导论—数据采集实战

一、数据科学导论——数据采集基本概念 第1关&#xff1a;巧妇难为无米之炊 第2关&#xff1a;数据采集概念与内涵 二、数据科学导论——数据采集实战 第1关&#xff1a;单网页爬取 import urllib.request import csv import re# ********** Begin ********** # dataurllib.r…...

微信小程序云开发教程——墨刀原型工具入门(素材面板)

引言 作为一个小白&#xff0c;小北要怎么在短时间内快速学会微信小程序原型设计&#xff1f; “时间紧&#xff0c;任务重”&#xff0c;这意味着学习时必须把握微信小程序原型设计中的重点、难点&#xff0c;而非面面俱到。 要在短时间内理解、掌握一个工具的使用&#xf…...

C#与WPF通用类库

个人集成封装&#xff0c;仓库已公开 NetHelper 集成了一些常用的方法&#xff1b; 如通用的缓存静态操作类、常用的Wpf的ValueConverters、内置的委托类型、通用的反射加载dll操作类、Wpf的ViewModel、Command、Navigation、Messenger、部分常用UserControls(可绑定的Passwo…...

http协议中的强缓存与协商缓存,带图详解

此篇抽自本人之前的文章&#xff1a;http面试题整理 。 别急着跳转&#xff0c;先把缓存知识学会了~ http中的缓存分为两种&#xff1a;强缓存、协商缓存。 强缓存 响应头中的 status 是 200&#xff0c;相关字段有expires&#xff08;http1.0&#xff09;,cache-control&…...

蓝桥杯2019年第十届省赛真题-修改数组

查重类题目&#xff0c;想到用标记数组记录是否出现过 但是最坏情况下可能会从头找到小尾巴&#xff0c;时间复杂度O(n2)&#xff0c;数据范围106显然超时 再细看下题目&#xff0c;我们重复进行了寻找是否出现过&#xff0c;干脆把每个元素出现过的次数k记录下来&#xff0c;直…...

【Python使用】python高级进阶知识md总结第3篇:静态Web服务器-返回指定页面数据,静态Web服务器-多任务版【附代码文档】

python高级进阶全知识知识笔记总结完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;操作系统&#xff0c;虚拟机软件&#xff0c;Ubuntu操作系统&#xff0c;Linux内核及发行版&#xff0c;查看目录命令&#xff0c;切换目录命令&#xff0c;绝对路径和相对…...

ELK 日志分析系统

ELK &#xff08;Elasticsearch、Logstash、Kibana&#xff09;日志分析系统的好处是可以集中查看所有服务器日志&#xff0c;减轻了工作量&#xff0c;从安全性的角度来看&#xff0c;这种集中日志管理可以有效查询以及跟踪服务器被攻击的行为。 Elasticsearch 是个开源分布式…...

机器学习模型—逻辑回归

机器学习模型—逻辑回归 逻辑回归是一种用于分类任务的监督机器学习算法,其目标是预测实例属于给定类别的概率。逻辑回归是一种分析两个数据因素之间关系的统计算法。本文探讨了逻辑回归的基础知识、类型和实现。 什么是逻辑回归 逻辑回归用于二元分类,其中我们使用sigmoi…...

​Ubuntu20.04 创建新的用户​

1、了解Linux目录结构 推荐看一下&#xff1a;https://www.runoob.com/linux/linux-system-contents.html Linux支持多个用户进行操作的&#xff0c;这样提高了系统的安全性&#xff0c;也可以多人共用一个系统&#xff0c;不过要注意的是系统中安装的软件相关路径&#xff0…...

大数据入门之hadoop学习

大数据 1. 学习hadoop之前&#xff0c;我们先了解一下什么是大数据&#xff1f; 大数据通常指的是数据集规模非常庞大且难以在常规数据库和数据处理工具中有效处理的数据。 大数据的特点&#xff1a; 容量&#xff1a;大数据具有庞大的规模&#xff0c;远远超出了传统数据库和…...

MySQL安装使用(mac、windows)

目录 macOS环境 一、下载MySQL 二、环境变量 三、启动 MySql 四、初始化密码设置 windows环境 一、下载 二、 环境配置 三、安装mysql 1.初始化mysql 2.安装Mysql服务 3.更改密码 四、检验 1.查看默认安装的数据库 2.其他操作 macOS环境 一、下载MySQL 打开 MyS…...

Day27:安全开发-PHP应用TP框架路由访问对象操作内置过滤绕过核心漏洞

目录 TP框架-开发-配置架构&路由&MVC模型 TP框架-安全-不安全写法&版本过滤绕过 思维导图 PHP知识点 功能&#xff1a;新闻列表&#xff0c;会员中心&#xff0c;资源下载&#xff0c;留言版&#xff0c;后台模块&#xff0c;模版引用&#xff0c;框架开发等 技…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...