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

算法leetcode|74. 搜索二维矩阵(rust重拳出击)


文章目录

  • 74. 搜索二维矩阵:
    • 样例 1:
    • 样例 2:
    • 提示:
  • 分析:
  • 题解:
    • rust:
    • go:
    • c++:
    • python:
    • java:


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

分析:

  • 面对这道算法题目,二当家的再次陷入了沉思。
  • 在有序列表中,查找指定元素,一般使用二分查找,非常高效。
  • 但是题目中是个二维矩阵,是否还能用二分查找呢?
  • 首先想到,可以用两次二分查找,分别看在哪行,再看在哪列,效率已经很高了,但是是否能只用一次二分查找呢?
  • 想要使用一次二分查找,就需要将二维矩阵转换成线性结构,有什么办法呢?
  • 我们可以快速算出矩阵的长和宽,也就可以拿到它的总长度,我们可以快速将长度范围内的下标,快速转换成行和列的下标,因为行列都是等长的。

题解:

rust:

impl Solution {pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {let (m, n) = (matrix.len(), matrix[0].len());let (mut left, mut right) = (0, m * n);while left < right {let mid = left + ((right - left) >> 1);let v = matrix[mid / n][mid % n];if v < target {left = mid + 1;} else if v > target {right = mid;} else {return true;}}return false;}
}

go:

func searchMatrix(matrix [][]int, target int) bool {m, n := len(matrix), len(matrix[0])i := sort.Search(m*n, func(i int) bool { return matrix[i/n][i%n] >= target })return i < m*n && matrix[i/n][i%n] == target
}

c++:

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {const int m = matrix.size(), n = matrix[0].size();int left = 0, right = m * n;while (left < right) {const int mid = left + ((right - left) >> 1);const int v = matrix[mid / n][mid % n];if (v < target) {left = mid + 1;} else if (v > target) {right = mid;} else {return true;}}return false;}
};

python:

class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:m, n = len(matrix), len(matrix[0])left, right = 0, m * nwhile left < right:mid = left + ((right - left) >> 1)v = matrix[mid // n][mid % n]if v < target:left = mid + 1elif v > target:right = midelse:return Truereturn False

java:

class Solution {public boolean searchMatrix(int[][] matrix, int target) {final int m = matrix.length, n = matrix[0].length;int left = 0, right = m * n;while (left < right) {final int mid = left + ((right - left) >> 1);final int v = matrix[mid / n][mid % n];if (v < target) {left = mid + 1;} else if (v > target) {right = mid;} else {return true;}}return false;}
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~


相关文章:

算法leetcode|74. 搜索二维矩阵(rust重拳出击)

文章目录 74. 搜索二维矩阵&#xff1a;样例 1&#xff1a;样例 2&#xff1a;提示&#xff1a; 分析&#xff1a;题解&#xff1a;rust&#xff1a;go&#xff1a;c&#xff1a;python&#xff1a;java&#xff1a; 74. 搜索二维矩阵&#xff1a; 给你一个满足下述两条属性的…...

element浅尝辄止7:InfiniteScroll 无限滚动

滚动加载&#xff1a;滚动至底部时&#xff0c;加载更多数据。 1.如何使用&#xff1f; //在要实现滚动加载的列表上上添加v-infinite-scroll&#xff0c;并赋值相应的加载方法&#xff0c; //可实现滚动到底部时自动执行加载方法。<template><ul class"infinit…...

Day05-Vue基础

Day05-Vue基础 一、单向数据流 父子组件通信。会在父组件中定义好数据,将数据传递给子组件,可以使用这个数据 Vue中针对props这个属性提出了一个单向数据流的概念。 Vue针对props做了一些限制,可以接受值,使用这个值,规范中不要去直接修改这个值 目的是为了对数据流进…...

《机器学习在车险定价中的应用》实验报告

目录 一、实验题目 机器学习在车险定价中的应用 二、实验设置 1. 操作系统&#xff1a; 2. IDE&#xff1a; 3. python&#xff1a; 4. 库&#xff1a; 三、实验内容 实验前的猜想&#xff1a; 四、实验结果 1. 数据预处理及数据划分 独热编码处理结果&#xff08;以…...

14. Docker中实现CI和CD

目录 1、前言 2、什么是CI/CD 3、部署Jenkins 3.1、下载Jenkins 3.2、启动Jenkins 3.3、访问Jenkins页面 4、Jenkins部署一个应用 5、Jenkins实现Docker应用的持续集成和部署 5.1、创建Dockerfile 5.2、集成Jenkins和Docker 6、小结 1、前言 持续集成(CI/CD)是一种…...

【多思路解决喝汽水问题】1瓶汽水1元,2个空瓶可以换一瓶汽水,给20元,可以喝多少汽水

题目内容 喝汽水问题 喝汽水&#xff0c;1瓶汽水1元&#xff0c;2个空瓶可以换一瓶汽水&#xff0c;给20元&#xff0c;可以喝多少汽水&#xff08;编程实现&#xff09;。 题目分析 数学思路分析 根据给出的问题和引用内容&#xff0c;我们可以得出答案。 首先&#xff…...

P1591 阶乘数码(Java高精度)

题目描述 求 n ! n! n! 中某个数码出现的次数。 输入格式 第一行为 t ( t ≤ 10 ) t(t \leq 10) t(t≤10)&#xff0c;表示数据组数。接下来 t t t 行&#xff0c;每行一个正整数 n ( n ≤ 1000 ) n(n \leq 1000) n(n≤1000) 和数码 a a a。 输出格式 对于每组数据&a…...

Mybatis的动态SQL及关键属性和标识的区别(对SQL更灵活的使用)

&#xff08; 虽然文章中有大多文本内容&#xff0c;想了解更深需要耐心看完&#xff0c;必定大有受益 &#xff09; 目录 一、动态SQL ( 1 ) 是什么 ( 2 ) 作用 ( 3 ) 优点 ( 4 ) 特殊标签 ( 5 ) 演示 二、#和$的区别 2.1 #使用 ( 1 ) #占位符语法 ( 2 ) #优点 2.…...

mysql下载

网址 MySQL :: Download MySQL Community Serverhttps://dev.mysql.com/downloads/mysql/ 2、选择MSI进行安装 3、这里我选择离线安装 4、这里我选择直接下载 5、等待下载安装即可...

聚合函数与窗口函数

聚合函数 回答一 聚合函数&#xff08;Aggregate Functions&#xff09;是SQL中的函数&#xff0c;用于对一组数据进行计算&#xff0c;并返回单个结果。聚合函数通常用于统计和汇总数据&#xff0c;包括计算总和、平均值、计数、最大值和最小值等。 以下是一些常见的聚合函…...

c语言实现堆

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、树1、树的概念2、树的相关概念3、树的表示 二、二叉树1、二叉树概念2、特殊的二叉树3、二叉树的性质4、二叉树的顺序结构5、二叉树的链式结构 三、堆(二叉树…...

ubuntu 如何将文件打包成tar.gz

要将文件打包成.tar.gz文件&#xff0c;可以使用以下命令&#xff1a; tar -czvf 文件名.tar.gz 文件路径 其中&#xff0c;-c表示创建新的归档文件&#xff0c;-z表示使用gzip进行压缩&#xff0c;-v表示显示详细的打包过程&#xff0c;-f表示指定归档文件的名称。 例如&am…...

前端优化页面加载速度的方法(持续更新)

提速方法方向 延迟脚本加载 使用 async 属性&#xff1a; 在这种方法中&#xff0c;脚本将在下载完成后立即执行&#xff0c;而不会阻塞其他页面资源的加载和渲染。这适用于那些不依赖于其他脚本和页面内容的脚本&#xff0c;例如分析脚本等。示例如下&#xff1a; html …...

利用SSL证书的SNI特性建立自己的爬虫ip服务器

今天我要和大家分享一个关于自建多域名HTTPS爬虫ip服务器的知识&#xff0c;让你的爬虫ip服务器更加强大&#xff01;无论是用于数据抓取、反爬虫还是网络调试&#xff0c;自建一个支持多个域名的HTTPS爬虫ip服务器都是非常有价值的。本文将详细介绍如何利用SSL证书的SNI&#…...

HTML和CSS

HTML HTML(Hyper Text Markup Language):超文本语言 超文本&#xff1a;超越了文本的限制&#xff0c;比普通文本更强大。除了文字信息&#xff0c;还可以定义图片、音频、视频等内容。 标记语言&#xff1a;由标签构成的语言 HTML标签都是预定义好的。例如&#xff1a;使用&l…...

C#的IndexOf

在 C# 中&#xff0c;IndexOf 是一个字符串、数组或列表的方法&#xff0c;用于查找指定元素的第一个匹配项的索引。它返回一个整数值&#xff0c;表示匹配项在集合中的位置&#xff0c;如果未找到匹配项&#xff0c;则返回 -1。 IndexOf 方法有多个重载形式&#xff0c;可以根…...

深度学习2.神经网络、机器学习、人工智能

目录 深度学习、神经网络、机器学习、人工智能的关系 大白话解释深度学习 传统机器学习 VS 深度学习 深度学习的优缺点 4种典型的深度学习算法 卷积神经网络 – CNN 循环神经网络 – RNN 生成对抗网络 – GANs 深度强化学习 – RL 总结 深度学习 深度学习、神经网络…...

利用LLM模型微调的短课程;钉钉宣布开放智能化底座能力

&#x1f989; AI新闻 &#x1f680; 钉钉宣布开放智能化底座能力AI PaaS&#xff0c;推动企业数智化转型发展 摘要&#xff1a;钉钉在生态大会上宣布开放智能化底座能力AI PaaS&#xff0c;与生态伙伴探寻企业服务的新发展道路。AI PaaS结合5G、云计算和人工智能技术的普及和…...

软件工程(七) UML之用例图详解

1、UML-4+1视图 UML-4+1视图将会与后面的架构4+1视图会一一对应上 视图往往出现在什么场景:我们看待一个事物,我们觉得它很复杂,难以搞清楚,为了化繁为简,我们会从一个侧面去看,这就是视图。而4+1视图就是分不同角度去看事物。 逻辑视图(logical view) 一般使用类与对…...

pd.cut()函数--Pandas

1. 函数功能 将连续性数值进行离散化处理&#xff1a;如对年龄、消费金额等进行分组 2. 函数语法 pandas.cut(x, bins, rightTrue, labelsNone, retbinsFalse, precision3, include_lowestFalse, duplicatesraise, orderedTrue)3. 函数参数 参数含义x要离散分箱操作的数组&…...

HunyuanVideo-Foley效果展示:为体育直播生成实时观众欢呼/球鞋摩擦/哨声

HunyuanVideo-Foley效果展示&#xff1a;为体育直播生成实时观众欢呼/球鞋摩擦/哨声 1. 惊艳的体育音效生成能力 想象一下&#xff0c;当篮球运动员急停变向时&#xff0c;球鞋与地板摩擦发出的"吱吱"声&#xff1b;当足球射门得分时&#xff0c;全场观众爆发的欢呼…...

Apache Tomcat 在 IDEA 中配置完整教程(手把手保姆教程)

目录 文章内容简介 配置前提 IDEA 准备 IDEA 中的配置 文章内容简介 本文详细介绍了在IDEA中配置Apache Tomcat服务器的完整步骤。首先指导用户创建Maven Archetype项目。重点讲解了Tomcat服务器的配置过程&#xff0c;包括设置服务器路径、部署工件、修改HTTP端口等关键操…...

项目介绍 MATLAB实现基于灰狼优化算法(GWO)进行无人机三维路径规划的详细项目实例(含模型描述及部分示例代码)

MATLAB实现基于灰狼优化算法&#xff08;GWO&#xff09;进行无人机三维路径规划的详细项目实例 更多详细内容可直接联系博主本人 或者访问以下链接地址 MATLAB实现基于灰狼优化算法&#xff08;GWO&#xff09;进行无人机三维路径规划的详细项目实例-CSDN博客 https://blo…...

思源宋体终极指南:免费商用中文字体解决方案从入门到精通

思源宋体终极指南&#xff1a;免费商用中文字体解决方案从入门到精通 【免费下载链接】source-han-serif-ttf Source Han Serif TTF 项目地址: https://gitcode.com/gh_mirrors/so/source-han-serif-ttf 还在为商业项目寻找高质量中文字体而烦恼&#xff1f;思源宋体这款…...

5大突破!漫画阅读工具Venera重构跨平台阅读体验

5大突破&#xff01;漫画阅读工具Venera重构跨平台阅读体验 【免费下载链接】venera A comic app 项目地址: https://gitcode.com/gh_mirrors/ve/venera 副标题&#xff1a;如何在Windows、macOS和移动设备间无缝切换你的漫画库&#xff1f; 开篇痛点引入 不同设备间漫…...

双模型混搭方案:OpenClaw同时接入百川2-13B与Qwen的实操演示

双模型混搭方案&#xff1a;OpenClaw同时接入百川2-13B与Qwen的实操演示 1. 为什么需要多模型混搭&#xff1f; 去年冬天&#xff0c;当我第一次尝试用OpenClaw自动化处理技术文档时&#xff0c;发现一个有趣的现象&#xff1a;同一个模型在不同任务上的表现差异巨大。Qwen在…...

三层交换机vlan间互通配置

SW1&#xff08;三层交换机&#xff09;配置# 1. 创建VLAN sysname LSW1 vlan batch 100 200 300# 2. 配置接口并加入VLAN interface GigabitEthernet 0/0/4port link-type accessport default vlan 100stp disable # 关闭生成树 interface GigabitEthernet 0/0/5port link-ty…...

从游戏报错到完美运行 DirectX修复工具实际应用案例展示

评价一款工具软件的优劣&#xff0c;最具有说服力的方式莫过于通过真实的实际案例来直观展示其效果和价值。 对于系统修复类工具来说&#xff0c;更是如此&#xff0c;因为用户最关心的就是它能否真正解决自己的问题。 DirectX相关问题一直是Windows游戏玩家最常遇到的技术难题…...

这次终于选对了!高效论文写作全流程AI论文写作软件推荐(2026 最新)

2026年AI论文写作软件已全面升级&#xff0c;论文写作全流程可拆解为文献调研→选题/开题→大纲/初稿→文献综述→降重/去AI味→润色/格式→查重/投稿七大环节&#xff0c;以下工具按环节精准匹配&#xff0c;兼顾中文适配、降重能力、去AI痕迹、学术合规四大核心需求&#xff…...

5款部署方案的开源UML工具:开发者与设计师的高效协作绘图平台

5款部署方案的开源UML工具&#xff1a;开发者与设计师的高效协作绘图平台 【免费下载链接】umlet Free UML Tool for Fast UML Diagrams 项目地址: https://gitcode.com/gh_mirrors/um/umlet 开源UML工具UMLet是一款专为高效绘图设计的跨平台解决方案&#xff0c;它通过…...