当前位置: 首页 > 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要离散分箱操作的数组&…...

做了十几年财务,我用RPA把最累的工作交给了“机器人”

在财务这行摸爬滚打了十几年&#xff0c;算是一路看着这个行业慢慢“进化”过来的&#xff1a;从最早拿计算器对数据&#xff0c;到后来用电脑做账&#xff0c;从手工账本过渡到ERP系统&#xff0c;再到这两年铺天盖地的“数智化转型”。中间也确实尝试过不少所谓的“黑科技”。…...

USB设备安全弹出工具终极指南:告别Windows繁琐移除,一键搞定所有存储设备

USB设备安全弹出工具终极指南&#xff1a;告别Windows繁琐移除&#xff0c;一键搞定所有存储设备 【免费下载链接】USB-Disk-Ejector A program that allows you to quickly remove drives in Windows. It can eject USB disks, Firewire disks and memory cards. It is a quic…...

果园灌溉施肥控制系统改造之西门子 S7 - 1200 PLC 实战

果园灌溉施肥控制系统改3 西门子s7-1200plc程序博途v16&#xff0c;带 选型表 io表接线图CAD和运行效果视频最近搞了个果园灌溉施肥控制系统的改造项目&#xff0c;用的是西门子 S7 - 1200 PLC&#xff0c;编程软件是博途 V16&#xff0c;这过程还挺有意思&#xff0c;跟大家…...

若依前后端分离系统生产环境部署:从零到上线的保姆级教程

若依前后端分离系统生产环境部署实战指南 引言&#xff1a;为什么选择若依框架&#xff1f; 对于刚接触企业级开发的新手来说&#xff0c;若依(RuoYi)框架无疑是一个绝佳的起点。这个基于Spring Boot和Vue.js的前后端分离架构&#xff0c;不仅提供了完善的权限管理、代码生成等…...

ROS2接口实战:从传感器数据到自定义消息的完整开发流程(附Python示例)

ROS2接口实战&#xff1a;从传感器数据到自定义消息的完整开发流程&#xff08;附Python示例&#xff09; 在机器人开发领域&#xff0c;数据的高效传递与标准化处理是系统稳定运行的关键。ROS2作为新一代机器人操作系统&#xff0c;其接口系统提供了强大的数据交换能力&#x…...

苹果内购Java后端避坑指南:沙盒测试、凭据验证与订单防重的那些事儿

苹果内购Java后端避坑指南&#xff1a;沙盒测试、凭据验证与订单防重的那些事儿 第一次对接苹果应用内购&#xff08;IAP&#xff09;时&#xff0c;我以为按照官方文档走完流程就万事大吉了。直到凌晨三点收到服务器告警——重复充值、验证超时、沙盒环境漏测等问题接踵而至。…...

从Solidworks到Simulink:避开ADAMS“雷区”的机电联合仿真实践

1. 为什么机电联合仿真总在ADAMS上栽跟头&#xff1f; 第一次用ADAMS做机电联合仿真时&#xff0c;我对着满屏的线框图发呆了半小时——这玩意儿怎么连个像样的实体显示都要手动切换&#xff1f;更崩溃的是&#xff0c;好不容易导入的Solidworks装配体&#xff0c;所有配合关系…...

Oracle RAC实战:5分钟搞懂SCAN IP和VIP的区别与配置技巧

Oracle RAC实战&#xff1a;SCAN IP与VIP的深度解析与高效配置指南 引言 在Oracle RAC&#xff08;Real Application Clusters&#xff09;环境中&#xff0c;高可用性和负载均衡是核心诉求。SCAN IP和VIP作为两大关键技术组件&#xff0c;常常让刚接触RAC的DBA感到困惑。它们虽…...

PyTorch 3.0静态图分布式训练源码分析窗口即将关闭:官方已标记torch.distributed._spmd模块为“实验性冻结”,2024 Q3后将移除调试钩子入口

第一章&#xff1a;PyTorch 3.0静态图分布式训练的演进背景与冻结决策动因PyTorch 3.0正式宣布冻结静态图&#xff08;TorchScript&#xff09;在分布式训练路径中的演进支持&#xff0c;这一决策并非技术倒退&#xff0c;而是基于多年大规模生产实践与生态协同的理性收敛。随着…...

机械键盘连击修复:这款智能工具如何拯救你的打字体验

机械键盘连击修复&#xff1a;这款智能工具如何拯救你的打字体验 【免费下载链接】KeyboardChatterBlocker A handy quick tool for blocking mechanical keyboard chatter. 项目地址: https://gitcode.com/gh_mirrors/ke/KeyboardChatterBlocker 当你在编写重要文档时&…...