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

C语言——实现杨氏矩阵

什么是杨氏矩阵?

概念:

有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增

eg:

1 2 3
4 5 6 
7 8 9

题目:

请编写程序在这样的矩阵中查找某个数字是否存在。

要求:时间复杂度小于O(N);

分析:

我们仔细分析,不难发现,对于杨氏矩阵来说,

右上角和左下角的元素是有特点的。

右上角的元素是一行中最大的,一列中最小的。

左下角的元素是一行中最小的,是一列中最大的。

所以我们可以从右上角或者左下角开始查找。

比如:

从右上角开始查找的时候,右上角的元素比我们要查找元素小,我们就可以去掉右上角元素所在的这一行;

右上角的元素比我们要查找的元素大,我们就可以去掉右上角元素所在的这一列。

然后依然找右上角的元素继续和要查找的元素与比较。

这样每一次比较去掉一行或者去掉一列。

这个查找效率是高于遍历数组元素的,所以时间复杂度是小于O(N),也满足题目要求。 

find_k(int arr[3][3], int r, int c,int k)
{int x = 0;int y = c - 1;while (1){if (arr[x][y] < k){arr[x][y] = arr[x++][y];//x++;}else if (arr[x][y] > k){arr[x][y] = arr[x][y--];//y--;}else{printf("找到了,位置为%d,%d", x, y);break;}}
}
int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int k = 7;find_k(arr, 3, 3,k);return 0;
}

优化:传地址过去,可以直接返回到主函数判断

int find_k(int arr[3][3], int *px, int *py, int k)
{int x = 0;int y = *py-1;int flag = 0;while (x <= *px - 1 && y>=0){if (arr[x][y] < k){x++;}else if (arr[x][y] > k){y--;}else{*px = x;*py = y;flag = 1;return 1;}}if (flag == 0)return 0;}
int main()
{int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };int k = 7;int x = 3;int y = 3;int ret =find_k(arr,&x,&y,k);if (ret == 0)printf("找不到了");if(ret ==1)printf("下标为%d,%d", x,y);return 0;
}

相关文章:

C语言——实现杨氏矩阵

什么是杨氏矩阵&#xff1f; 概念&#xff1a; 有一个数字矩阵&#xff0c;矩阵的每行从左到右是递增的&#xff0c;矩阵从上到下是递增的 eg&#xff1a; 1 2 3 4 5 6 7 8 9 题目&#xff1a; 请编写程序在这样的矩阵中查找某个数字是否存在。 要求&#xff1a;时间复…...

授权模型PAM

PAM&#xff08;Privileged Access Management&#xff09;是一种授权模型&#xff0c;用于管理和控制特权用户的访问权限。PAM的目标是确保特权用户只能在需要时获得所需的特权&#xff0c;并且他们的活动得到适当的监控和审计。 PAM的核心思想是将特权访问权限视为一种受限的…...

【Leecode】子集⭐⭐

子集 [78]子集I 题目描述 给你一个整数数组 nums &#xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集&#xff08;幂集&#xff09;。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例输入 示例 1&#xff1a; 输入&#xff1a;nums [1, 2, 3…...

Linux高性能服务器编程 | 读书笔记 | 12. 多线程编程

12. 多线程编程 注&#xff1a;博客中有书中没有的内容&#xff0c;均是来自 黑马06-线程概念_哔哩哔哩_bilibili 早期Linux不支持线程&#xff0c;直到1996年&#xff0c;Xavier Leroy等人开发出第一个基本符合POSIX标准的线程库LinuxThreads&#xff0c;但LinuxThreads效率…...

[HNCTF 2022 Week1]baby_rsa

源代码&#xff1a; from Crypto.Util.number import bytes_to_long, getPrime from gmpy2 import * from secret import flag m bytes_to_long(flag) p getPrime(128) q getPrime(128) n p * q e 65537 c pow(m,e,n) print(n,c) # 62193160459999883112594854240161159…...

解析Java中的Stream API:函数式编程与性能优化

自Java 8以来&#xff0c;Java语言引入了Stream API&#xff0c;为开发者提供了一种全新的数据处理方式。Stream API支持函数式编程风格&#xff0c;使得对集合、数组、IO流等数据源的操作更加简洁、直观且具有高效的性能优势。通过Stream API&#xff0c;我们可以在不修改原有…...

java简单题目练习

大家好&#xff0c;今天我们不学习新的内容&#xff0c;今天给大家分享一些简单的java算法题供大家练练手&#xff0c;那么我们下面就来看看。 那么大家下去练习一下&#xff0c;我们明天继续讲解类和对象的相关知识&#xff0c;谢谢大家&#xff01;&#xff01;&#xff01;...

Kaggler日志--Day9

进度24/12/18 昨日复盘&#xff1a; 补充并解决Day7Kaggler日志–Day7统计的部分问题 今日进度&#xff1a; 继续完成Day8Kaggler日志–Day8统计问题的解答 明日规划&#xff1a; 今天报名了Regression with an Insurance Dataset算是新手村练习比赛&#xff0c;截止时间是2…...

OpenCVE:一款自动收集NVD、MITRE等多源知名漏洞库的开源工具,累计收录CVE 27万+

漏洞库在企业中扮演着至关重要的角色&#xff0c;不仅提升了企业的安全防护能力&#xff0c;还支持了安全决策、合规性要求的满足以及智能化管理的发展。前期博文《业界十大知名权威安全漏洞库介绍》介绍了主流漏洞库&#xff0c;今天给大家介绍一款集成了多款漏洞库的开源漏洞…...

麒麟信安参编的《能源企业数字化转型能力评价 技术可控》团体标准发布

近日&#xff0c;中国能源研究会发布公告&#xff0c;《能源企业数字化转型能力评价 技术可控》团体标准发布。该标准由麒麟信安与国网湖北省电力有限公司武汉供电公司、国网智能电网研究院有限公司、中能国研&#xff08;北京&#xff09;电力科学研究院等单位联合编制。 《能…...

戴尔物理机更换完Raid控制器(阵列卡),启动服务器失败

背景 我们使用的物理机是戴尔的POWEREDGE R730机器&#xff0c;由于硬件损坏导致该问题的延申&#xff0c;再更换完Raid的控制器&#xff08;阵列卡&#xff09;之后导致启动服务器报错。 报错&#xff1a; There are offline or missing virtual drives with preserved cac…...

计算机基础知识——数据结构与算法(二)(山东省大数据职称考试)

大数据分析应用-初级 第一部分 基础知识 一、大数据法律法规、政策文件、相关标准 二、计算机基础知识 三、信息化基础知识 四、密码学 五、大数据安全 六、数据库系统 七、数据仓库. 第二部分 专业知识 一、大数据技术与应用 二、大数据分析模型 三、数据科学 大数据相关标准…...

docsify

macos ➜ ~ node -v v16.20.2➜ ~ npm --version 8.19.4全局安装 docsify-cli 工具 npm i docsify-cli -g➜ ~ docsify -vdocsify-cli version:4.4.4初始化项目 docsify init ./docsls -ah docs . .. .nojekyll README.md index.htmlindex.html 入口文件README.md 会…...

GEE教程——使用 CHIRPS 和 GSMaP 数据集计算并可视化了特定区域的降水量

目录 简介 函数 ee.Image.pixelLonLat() No arguments. Returns: Image visualize(bands, gain, bias, min, max, gamma, opacity, palette, forceRgbOutput) Arguments: Returns: Image 代码解释 代码 结果 简介 GEE教程——使用 CHIRPS 和 GSMaP 数据集计算并可视…...

前端实现页面自动播放音频方法

前端实现页面视频在谷歌浏览器中自动播放音频方法 了解Chrome自动播放策略 在Chrome和其他现代浏览器中&#xff0c;为了改善用户体验&#xff0c;自动播放功能受到了限制。Chrome的自动播放策略主要针对有声音的视频&#xff0c;目的是防止页面在用户不知情的情况下自动播放声…...

【Nginx-5】Nginx 限流配置指南:保护你的服务器免受流量洪峰冲击

在现代互联网应用中&#xff0c;流量波动是常态。无论是突发的用户访问高峰&#xff0c;还是恶意攻击&#xff0c;都可能导致服务器资源耗尽&#xff0c;进而影响服务的可用性。为了应对这种情况&#xff0c;限流&#xff08;Rate Limiting&#xff09;成为了一种常见的保护措施…...

【芯片设计- RTL 数字逻辑设计入门 番外篇 7.1 -- 基于ATE的IC测试原理】

文章目录 ATE 测试概述Opens/Shorts测试Leakage测试AC测试转自:漫谈大千世界 漫谈大千世界 2024年10月23日 23:17 湖北 ATE 测试概述 ATE(Automatic Test Equipment)是用于检测集成电路(IC)功能完整性的自动测试设备。它在半导体产业中扮演着至关重要的角色,主要用于检…...

SurfaceFlinger 学习

Android 图形系统之七&#xff1a;SurfaceFlinger-CSDN博客 CSDN...

Flink SQL 从一个SOURCE 写入多个Sink端实例

一. 背景 FLINK 任务从一个数据源读取数据, 写入多个sink端. 二. 官方实例 写入多个Sink语句时&#xff0c;需要以BEGIN STATEMENT SET;开头&#xff0c;以END;结尾。--源表 CREATE TEMPORARY TABLE datagen_source (name VARCHAR,score BIGINT ) WITH (connector datagen …...

python飞机大战游戏.py

python飞机大战游戏.py import pygame import random# 游戏窗口大小 WINDOW_WIDTH 600 WINDOW_HEIGHT 800# 颜色定义 BLACK (0, 0, 0) WHITE (255, 255, 255)# 初始化Pygame pygame.init()# 创建游戏窗口 window pygame.display.set_mode((WINDOW_WIDTH, WINDOW_HEIGHT))…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...