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

【LeetCode 热题100】74:搜索二维矩阵(二分、线性两种方式 详细解析)(Go 语言实现)

🚀 力扣热题 74:搜索二维矩阵(详细解析)

📌 题目描述

力扣 74. 搜索二维矩阵

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

  1. 每行中的整数从左到右按非递减顺序排列。
  2. 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 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
  • -10^4 <= matrix[i][j], target <= 10^4

💡 解题思路

1. 观察矩阵特性

  • 矩阵每行递增,且下一行的第一个元素大于上一行的最后一个元素。
  • 可以将其视为一个 一维有序数组,索引从 0m * n - 1,然后用 二分查找 解决。

2. 方法一:二分查找

  1. 视整个二维数组为一维数组,使用索引 mid,计算对应的二维坐标:
    row = mid // n  (行号)
    col = mid % n  (列号)
    
  2. 进行标准的 二分查找
    • 如果 matrix[row][col] == target,返回 true
    • 如果 matrix[row][col] < target,移动左边界。
    • 如果 matrix[row][col] > target,移动右边界。
💻 Go 代码实现(方法一:二分查找)
func searchMatrix(matrix [][]int, target int) bool {if len(matrix) == 0 || len(matrix[0]) == 0 {return false}m, n := len(matrix), len(matrix[0])left, right := 0, m*n-1for left <= right {mid := (left + right) / 2row, col := mid/n, mid%nif matrix[row][col] == target {return true} else if matrix[row][col] < target {left = mid + 1} else {right = mid - 1}}return false
}

3. 方法二:逐行扫描 + 线性查找

  1. 遍历每一行,判断 target 是否在当前行范围内(即 row[0] <= target <= row[n-1])。
  2. 如果在范围内,则进行遍历查找。
  3. 适用于矩阵较小的情况,时间复杂度较高。
💻 Go 代码实现(方法二:逐行扫描)
func searchMatrix(matrix [][]int, target int) bool {for i := range matrix {num := matrix[i]if num[0] <= target && target <= num[len(num)-1] {for j := range num {if num[j] == target {return true}}}}return false
}

⏳ 复杂度分析

方法时间复杂度空间复杂度适用场景
🚀 二分查找 O ( log ⁡ ( m × n ) ) O(\log(m \times n)) O(log(m×n)) O ( 1 ) O(1) O(1)适用于大规模矩阵搜索
📌 逐行扫描 O ( m × n ) O(m \times n) O(m×n) O ( 1 ) O(1) O(1)适用于较小矩阵

🎯 总结

  • ✅ 方法一(推荐)二分查找,时间复杂度 O ( log ⁡ ( m × n ) ) O(\log(m \times n)) O(log(m×n)),适用于大规模数据。
  • 📌 方法二逐行扫描 + 线性查找,适用于数据量较小的情况。
  • 💡 掌握不同方法,有助于应对不同的面试场景!

👍 如果觉得有帮助,欢迎点赞、收藏、关注哦!

相关文章:

【LeetCode 热题100】74:搜索二维矩阵(二分、线性两种方式 详细解析)(Go 语言实现)

&#x1f680; 力扣热题 74&#xff1a;搜索二维矩阵&#xff08;详细解析&#xff09; &#x1f4cc; 题目描述 力扣 74. 搜索二维矩阵 给你一个满足下述两条属性的 m x n 整数矩阵 matrix &#xff1a; 每行中的整数从左到右按非递减顺序排列。每行的第一个整数大于前一行的…...

元数据、数据元、数据元素、数据项 和 主数据的概念

一、元数据 1.概念 元数据&#xff0c;又称中介数据、中继数据&#xff0c;为描述数据的数据。主要是描述数据属性的信息&#xff0c;用来支持如指示存储位置、历史数据、资源查找、文件记录等功能。 2.实例 数据库中&#xff0c;表的名称、表字段名、其他相关的描述信息&a…...

阿里云cdn怎样设置图片压缩

阿里云 CDN 提供了图像加速服务&#xff0c;其中包括图像压缩功能。通过设置图片压缩&#xff0c;可以显著减小图片文件的体积&#xff0c;提升网站加载速度&#xff0c;同时减少带宽消耗。九河云来告诉你如何进行图片压缩吧。 如何设置阿里云 CDN 图片压缩&#xff1f; 1. 登…...

白话文实战Nacos(保姆级教程)

前言 上一篇博客 我们创建好了微服务项目,本篇博客来体验一下Nacos作为注册中心和配置中心的功能。 注册中心 如果我们启动了一个Nacos注册中心,那么微服务比如订单服务,启动后就可以连上注册中心把自己注册上去,这过程就是服务注册。每个微服务,比如商品服务都应该注册…...

7. 基于DeepSeek和智谱清言实现RAG问答

课件链接&#xff1a;https://cloud.189.cn/t/VNvmyimY7Vna&#xff08;访问码&#xff1a;e4cb&#xff09;天翼云盘是中国电信推出的云存储服务&#xff0c;为用户提供跨平台的文件存储、备份、同步及分享服务&#xff0c;是国内领先的免费网盘&#xff0c;安全、可靠、稳定、…...

【数据结构】双向链表(真正的零基础)

链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过指针的链接来实现的&#xff01;在上篇我们学习了单向链表&#xff0c;而单向链表虽然空间利用率高&#xff0c;插入和删除也只需改变指针就可以达到&#xff01;但是我们在每次查找、删除、访问..…...

【生产变更】- Oracle RAC添加配置ipv6地址

【生产变更】- Oracle RAC添加配置ipv6地址 一、概述二、环境检查及备份2.1 检查并备份系统层面IP配置2.2 检查并备份监听配置2.3 检查并备份网卡配置2.4 检查并备份/etc/hosts三、集群层面配置3.1 检查集群配置3.2 停止集群组件3.3 Bond0网卡设置3.4 /etc/hosts文件配置3.5 重…...

Ai无限免费生成高质量ppt教程(deepseek+kimi)

第一步&#xff1a;打开deepseek官网&#xff08;DeepSeek) 1.如果deepseek官网网络繁忙&#xff0c;解决方案如下&#xff1a; (1)使用easychat官网&#xff08;EasyChat&#xff09;使用deepseek模型&#xff0c;如图所示&#xff1a; &#xff08;2&#xff09;本地部署&…...

python全栈-python基础

python基础 文章目录 python基础python入门基础概念序列列表元组 -- 不可变序列字典字典的本质集合 控制语句选择结构 - 条件判断结构循环结构zip()推导式 函数及原理参数LEGB规则 面向对象私有属性和私有方法面向对象的特征重写__str__()方法super获得父类的定义特殊方法和运算…...

Python 鼠标轨迹 - 防止游戏检测

一.简介 鼠标轨迹算法是一种模拟人类鼠标操作的程序&#xff0c;它能够模拟出自然而真实的鼠标移动路径。 鼠标轨迹算法的底层实现采用C/C语言&#xff0c;原因在于C/C提供了高性能的执行能力和直接访问操作系统底层资源的能力。 鼠标轨迹算法具有以下优势&#xff1a; 模拟…...

力扣 零钱兑换

完全背包&#xff0c;动态规划例题。 题目 这题跟完全背包跟完全平方数有点相似。在完全平方数中&#xff0c;用一个dp数组去取得目标金额的每一步的最优&#xff0c;当前状态可能来自上一个dp&#xff0c;也有可能比上一个dp更小&#xff0c;因此往回退一步加一做比较。在完全…...

C# OpenCV机器视觉:OSTU算法实现背景差分的自适应分割

在一个热闹的科技公司里&#xff0c;阿强是一个负责图像分析的员工。他的日常工作就是从各种复杂的图像中提取出有用的信息&#xff0c;可这可不是一件轻松的事情哦 最近&#xff0c;阿强接到了一个艰巨的任务&#xff1a;要从一堆嘈杂的监控图像中分离出运动的物体&#xff0c…...

快速搭建 Elasticsearch 8 集群:零基础实战与升级注意事项

引言 随着大数据技术的飞速发展,Elasticsearch 成为许多应用场景中不可或缺的技术,它以其高效的全文搜索引擎和分布式存储架构在企业和个人项目中占据了一席之地。无论是在日志分析、实时搜索还是数据可视化中,Elasticsearch 都发挥着重要的作用。 在这篇文章中,我们将为…...

基于扑克牌分发效果制作时的问题总结

其基本效果如图 1. 在overlay模式下直接使用position来移动 实现代码 public class Card : MonoBehaviour {public RectTransform target;public Button cardButton;private bool isPack false;public List<RectTransform> cards new List<RectTransform>(…...

老榕树的Java专题:Redis 从入门到实践

一、引言 在当今的软件开发领域&#xff0c;数据的高效存储和快速访问是至关重要的。Redis&#xff08;Remote Dictionary Server&#xff09;作为一个开源的、基于内存的数据结构存储系统&#xff0c;因其高性能、丰富的数据类型和广泛的应用场景&#xff0c;成为了众多开发者…...

【玩转 Postman 接口测试与开发2_019】第15章:利用 Postman 初探 API 性能测试(含实战截图)

《API Testing and Development with Postman》最新第二版封面 文章目录 第十五章 API 接口性能测试1 性能负载的类型2 Postman 负载配置3 Postman 性能测试实战3.1 Fixed 型负载下的性能测试3.2 基于数据驱动的 Postman 接口性能测试 4 性能测试的注意事项 写在前面 终于来到了…...

在 Qt 开发中,可以将 QML 封装成库

在 Qt 开发中&#xff0c;可以将 QML 封装成库&#xff0c;以便在多个项目中复用 QML 组件或模块。下面通过一个简单的例子说明如何将 QML 封装成库并在其他项目中使用。 1. 创建 QML 库项目 首先&#xff0c;我们创建一个新的 Qt 项目&#xff0c;专门用于封装 QML 组件。假…...

换电脑了如何快速导出vscode里的插件

当你换电脑了&#xff0c;之前vscode里的插件又不想全部手动重装&#xff0c;那么恭喜你&#xff0c;刷到了这篇文章。 1. 将 VSCode 添加到系统路径 macOS 打开 VSCode。按下 Command Shift P 打开命令面板。 3。 输入 Shell Command: Install ‘code’ command in PATH …...

点大商城V2-2.6.6源码全开源uniapp +搭建教程

一.介绍 点大商城V2独立开源版本&#xff0c;版本更新至2.6.6&#xff0c;系统支持多端&#xff0c;前端为UNiapp&#xff0c;多端编译。 二.搭建环境&#xff1a; 系统环境&#xff1a;CentOS、 运行环境&#xff1a;宝塔 Linux 网站环境&#xff1a;Nginx 1.21 MySQL 5.…...

9 Pydantic复杂数据结构的处理

在构建现代 Web 应用时&#xff0c;我们往往需要处理复杂的输入和输出数据结构。例如&#xff0c;响应数据可能包含嵌套字典、列表、元组&#xff0c;甚至是多个嵌套对象。Pydantic 是一个强大的数据验证和序列化库&#xff0c;可以帮助我们轻松地处理这些复杂的数据结构&#…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...