当前位置: 首页 > 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领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 🍅文末获取源码联系🍅…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

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

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

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...

基于小程序老人监护管理系统源码数据库文档

摘 要 近年来&#xff0c;随着我国人口老龄化问题日益严重&#xff0c;独居和居住养老机构的的老年人数量越来越多。而随着老年人数量的逐步增长&#xff0c;随之而来的是日益突出的老年人问题&#xff0c;尤其是老年人的健康问题&#xff0c;尤其是老年人产生健康问题后&…...

ffmpeg(三):处理原始数据命令

FFmpeg 可以直接处理原始音频和视频数据&#xff08;Raw PCM、YUV 等&#xff09;&#xff0c;常见场景包括&#xff1a; 将原始 YUV 图像编码为 H.264 视频将 PCM 音频编码为 AAC 或 MP3对原始音视频数据进行封装&#xff08;如封装为 MP4、TS&#xff09; 处理原始 YUV 视频…...