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

【算法】【数组与矩阵模块】在排好序的矩阵中找数,时间复杂度O(M+N)

目录

  • 前言
  • 问题介绍
  • 解决方案
  • 代码编写
    • java语言版本
    • c语言版本
    • c++语言版本
  • 思考感悟
  • 写在最后

前言

当前所有算法都使用测试用例运行过,但是不保证100%的测试用例,如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识!

问题介绍

原问题
给定二维数组arr,arr为排好序的数组,其中arr同时满足,从左到右递增,从上到下递增,给定一个数k,在尽可能少的时间内找到数k即可
如:
arr = [0125234744485779]\begin{bmatrix} 0 & 1 & 2 & 5 \\ 2 & 3 & 4 & 7 \\ 4 & 4 & 4 & 8 \\ 5 & 7 & 7 & 9 \end{bmatrix}0245134724475789
k = 7
结果:true

解决方案

原问题
假设arr为N*M的矩阵
1、从右上角或者左下角开始,如果k < arr[N][0] ,说明k一定小于arr的第N行,行–
2、如果k > arr[N][0] ,说明k一定大于arr的第0列,列++
3、通过以上规则,查找到数后返回true,找不到并且越界后则退出循环,返回false

代码编写

java语言版本

原问题:

/*** 二轮测试:在排好序的矩阵中找数* @param arr* @param k* @return*/public static boolean isContainsCp1(int[][] arr, int k) {if (arr == null || arr.length == 0) {return false;}int row = arr.length - 1;int col = 0;while (row >= 0 && col <= arr[0].length - 1) {int cur = arr[row][col];if (cur == k) {return true;}else if (cur > k) {// 当前行不会存在krow--;}else {// 当前列不会存在kcol++;}}return false;}public static void main(String[] args) {System.out.println(isContainsCp1(new int[][]{{0,1,2,5},{2,3,4,7},{4,4,4,8},{5,7,7,9}}, 7));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

每一次的比较都能够至少排除一行或者一列,这个速度应该是比较快的了,如果大家有更好的办法记得评论区各显神通哦~

写在最后

方案和代码仅提供学习和思考使用,切勿随意滥用!如有错误和不合理的地方,务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津!

相关文章:

【算法】【数组与矩阵模块】在排好序的矩阵中找数,时间复杂度O(M+N)

目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言 当前所有算法都使用测试用例运行过&#xff0c;但是不保证100%的测试用例&#xff0c;如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识&#xff01; 问题介绍 …...

【Java|基础篇】计算机中数据的存储规则

文章目录前言:1.计算机中的数据2.二进制的介绍二进制的运算规则常见的进制3.字符的存储4.汉字的存储5.图片的存储6.音频的存储总结:前言: 本篇文章只是为了科普 计算机中数据的存储规则 1.计算机中的数据 计算机的数据大致分为三类:文本数据,图片和音频 注:视频是图片和音频…...

RestTemplate使用HttpClient连接池

文章目录RestTemplate使用HttpClient连接池ClientHttpRequestFactorySimpleClientHttpRequestFactorySimpleClientHttpRequestFactory 设置超时时间HttpURLConnection的缺点HttpComponentsClientHttpRequestFactoryPoolingHttpClientConnectionManager配置连接池HttpClient总结…...

Python 操作Redis

在 Python中我们使用 redis库来操作 Redis数据库。Redis数据库的使用命令这里就不介绍了。 需要安装 redis库。检查是否安装redis&#xff1a; pip redis 如果未安装&#xff0c;使用 pip命令安装 redis。 pip install redis #安装最新版本 一、Redis连接 Redis提供两个类 Re…...

CEC2020:鱼鹰优化算法(Osprey optimization algorithm,OOA)求解CEC2020(提供MATLAB代码

一、鱼鹰优化算法简介 鱼鹰优化算法&#xff08;Osprey optimization algorithm&#xff0c;OOA&#xff09;由Mohammad Dehghani 和 Pavel Trojovsk于2023年提出&#xff0c;其模拟鱼鹰的捕食行为。 鱼鹰是鹰形目、鹗科、鹗属的仅有的一种中型猛禽。雌雄相似。体长51-64厘米…...

词对齐 - MGIZA++

文章目录关于 MGIZAgiza-py安装 MGIZA命令说明mkclsd4normhmmnormplain2sntsnt2coocsnt2coocrmpsnt2plainsymalmgizageneral parameters:No. of iterations:parameter for various heuristics in GIZA for efficient training:parameters for describing the type and amount o…...

GUI 之 Tkinter编程

GUI 图形界面&#xff0c;Tkinter 是 Python 内置的 GUI 库&#xff0c;IDLE 就是 Tkinter 设计的。 1. Tkinter 之初体验 import tkinter as tkroot tk.Tk() # 创建一个窗口root.title(窗口标题)# 添加 label 组件 theLabel tk.Label(root, text文本内容) theLabel.p…...

【软件测试】性能测试面试题都问什么?面试官想要什么?回答惊险避坑......

目录&#xff1a;导读前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09;前言 1、你认为不同角色关…...

后端开发基础能力以及就Java的主流开发框架介绍

前言&#xff1a;java语言开发转后端&#xff0c;必须了解后端主流的一些东西&#xff0c;共勉。 后端开发需要具备以下基础能力&#xff1a; 1.编程语言&#xff1a;熟练掌握至少一门编程语言&#xff0c;如Java、Python、Ruby、PHP、C#等。 2.数据结构和算法&#xff1a;具…...

H2数据库连接时用户密码错误:Wrong user name or password [28000-214] 28000/28000 (Help)

H2数据库连接时用户密码错误: 2023-03-03 08:25:07 database: wrong user or password; user: "SA" org.h2.message.DbException: Wrong user name or password [28000-214]出现的问题配置信息原因解决办法org.h2.message.DbException: Wrong user name or password …...

青岛诺凯达机械盛装亮相2023济南生物发酵展,3月与您相约

BIO CHINA生物发酵展&#xff0c;作为生物发酵产业一年一度行业盛会&#xff0c;由中国生物发酵产业协会主办&#xff0c;上海信世展览服务有限公司承办&#xff0c;2023第10届国际生物发酵展&#xff08;济南&#xff09;于2023年3月30-4月1日在山东国际会展中心&#xff08;济…...

【JAVA程序设计】【C00111】基于SSM的网上图书商城管理系统——有文档

基于SSM的网上图书商城管理系统——有文档项目简介项目获取开发环境项目技术运行截图项目简介 基于ssm框架开发的网上在线图书售卖商城项目&#xff0c;本项目分为三种权限&#xff1a;系统管理员、卖家、买家 管理员角色包含以下功能&#xff1a; 用户信息管理、权限管理、订…...

基于卷积神经网络CNN的三相故障识别

目录 背影 卷积神经网络CNN的原理 卷积神经网络CNN的定义 卷积神经网络CNN的神经元 卷积神经网络CNN的激活函数 卷积神经网络CNN的传递函数 卷积神经网络CNN手写体识别 基本结构 主要参数 MATALB代码 结果图 展望 背影 现在生活&#xff0c;为节能减排&#xff0c;减少电能损…...

Java工厂设计模式详解,大厂的Java抽象工厂模式分享!

我是好程序员-小源&#xff01;本期文章主要给大家分享&#xff1a;Java工厂设计模式。文中使用通俗易懂的案例&#xff0c;使你快速学习和轻松上手&#xff01;一、什么是Java抽象工厂模式1. Java抽象工厂是23种设计模式中创建型模式的一种&#xff0c;Java抽象工厂是由多个工…...

Git 企业级分支提交流程

Git 企业级分支提交流程 首先在本地分支hfdev上进行开发&#xff0c;开发后要经过测试。 如果测试通过了&#xff0c;那么久可以合并到本地分支develop&#xff0c;合并之后hfdev和development应该完全一样。 git add 文件 git commit -m ‘注释’ git checkout develop //切换…...

C/C++每日一练(20230303)

目录 1. 字符串相乘 2. 单词拆分 II 3. 串联所有单词的子串 1. 字符串相乘 给定两个以字符串形式表示的非负整数 num1 和 num2&#xff0c;返回 num1 和 num2 的乘积&#xff0c;它们的乘积也表示为字符串形式。 示例 1: 输入: num1 "2", num2 "3"…...

Python3-条件控制

Python3 条件控制 Python 条件语句是通过一条或多条语句的执行结果&#xff08;True 或者 False&#xff09;来决定执行的代码块。 可以通过下图来简单了解条件语句的执行过程: 代码执行过程&#xff1a; if 语句 Python中if语句的一般形式如下所示&#xff1a; if condi…...

KDZD地埋电缆故障测试仪

一、产品特性 ★电缆故障测试仪&#xff08;闪测仪&#xff09; &#xff08;1&#xff09;使用范围广&#xff1a;用于测量各种不同截面、不同介质的各种电力电缆、高频同轴电缆&#xff0c;市话电缆及两根以上均匀铺设的地埋电线等电缆高低阻、短路、开路、断线以及高阻泄漏…...

爆款升级!新系列南卡Neo最强旗舰杀到,业内首款无线充骨传导耳机!

中国专业骨传导耳机品牌NANK南卡于近日发布了全新南卡Neo骨传导运动耳机&#xff0c;打造一款佩戴最舒适、音质体验最好的骨传导耳机。推出第2代声学響科技技术&#xff0c;提供更优质的开放式骨传导听音体验&#xff0c;透过不一样的音质体验&#xff0c;打造更好的骨传导耳机…...

基于Spring Boot+Thymeleaf的在线投票系统

文章目录 项目介绍主要功能截图:后台登录注册个人信息展示投票数据显示首页展示对战匹配分数排行榜部分代码展示设计总结项目获取方式🍅 作者主页:Java韩立 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 🍅文末获取源码联系🍅…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving

地址&#xff1a;LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂&#xff0c;正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...