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

[c语言日寄]在不完全递增序中查找特定要素

在这里插入图片描述

【作者主页】siy2333
【专栏介绍】⌈c语言日寄⌋:这是一个专注于C语言刷题的专栏,精选题目,搭配详细题解、拓展算法。从基础语法到复杂算法,题目涉及的知识点全面覆盖,助力你系统提升。无论你是初学者,还是进阶开发者,这里都能满足你的需求!
【食用方法】1.根据题目自行尝试 2.查看基础思路完善题解 3.学习拓展算法
【Gitee链接】资源保存在我的Gitee仓库:https://gitee.com/siy2333/study


文章目录

  • 前言
  • 一、题目引入
    • 不完全递增矩阵
    • 问题描述
  • 二、知识点分析
  • 三、解法实现与分析
    • 1. 暴力搜索
    • 2. 逐行二分查找
  • 四、总结


前言

查找类问题是一个非常常见的任务。无论是从简单的数组中查找一个特定的数字,还是从复杂的数据结构中检索信息,查找算法的效率和正确性都十分重要。今天,我们将探讨一个有趣的查找问题:在不完全递增序的矩阵中查找特定的元素。


一、题目引入

不完全递增矩阵

假设我们有一个二维矩阵,矩阵的每一行从左到右是递增的,但列与列之间并没有严格的递增关系。这种矩阵被称为“不完全递增序矩阵”。

例如,以下矩阵满足这一条件

1357
2468
10111213
9141516

在这个矩阵中,每一行都是递增的,但列与列之间并不完全递增

问题描述

给定一个不完全递增序的矩阵和一个目标数字,编写一个程序来判断该数字是否存在于矩阵中。
假设矩阵如下,而且目标数字为 12:

1357
2468
10111213
9141516

此时,程序返回 true。

二、知识点分析

  1. 矩阵的特性
    矩阵的每一行从左到右是递增的,这意味着我们可以利用这一特性来优化查找算法。虽然列与列之间没有严格的递增关系,但行的递增性仍然可以为我们提供一些线索。我们在接下来的文章中会利用这一点解题。
  2. 查找算法
    在完全有序的矩阵中,我们可以从右上角或左下角开始查找,利用矩阵的有序性逐步缩小搜索范围(例如二分查找)。然而,在不完全递增序的矩阵中,这种方法不再适用。我们需要寻找一种新的策略来优化查找过程。
  3. 时间复杂度
    对于一个 M×N 的矩阵,暴力搜索的时间复杂度为 O(M×N)。

三、解法实现与分析

1. 暴力搜索

最简单的查找方法是暴力搜索,即遍历矩阵的每一个元素,检查是否等于目标值。这种方法的时间复杂度为 O(M×N),效率较低。

#include <stdio.h>
#include <stdbool.h>#define M 4
#define N 4//暴力查找函数
bool find_brute_force(int matrix[M][N], int target) {for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {if (matrix[i][j] == target) {return true;}}}return false;
}
//主函数
int main() {//定义数组int matrix[M][N] = {{1, 3, 5, 7},{2, 4, 6, 8},{10, 11, 12, 13},{9, 14, 15, 16}};int target = 12;//查找与输出if (find_brute_force(matrix, target)) {printf("Target %d found in the matrix.\n", target);} else {printf("Target %d not found in the matrix.\n", target);}return 0;
}

运行结果如下:
请添加图片描述

2. 逐行二分查找

虽然矩阵的列没有严格的递增关系,但每一行的递增性可以被利用。我们可以对每一行进行二分查找。这种方法的时间复杂度为 O(MlogN)

#include <stdio.h>
#include <stdbool.h>#define M 4
#define N 4bool binary_search(int arr[], int target) {int left = 0, right = N - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return true;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return false;
}bool find_row_wise(int matrix[M][N], int target) {for (int i = 0; i < M; i++) {if (binary_search(matrix[i], target)) {return true;}}return false;
}int main() {int matrix[M][N] = {{1, 3, 5, 7},{2, 4, 6, 8},{10, 11, 12, 13},{9, 14, 15, 16}};int target = 12;if (find_row_wise(matrix, target)) {printf("Target %d found in the matrix.\n", target);} else {printf("Target %d not found in the matrix.\n", target);}return 0;
}

运行结果如下:
请添加图片描述

四、总结

通过分析条件的特性,选择合适的查找算法和数据结构,是程序员的重要素质。对于这道题,即不完全递增序的矩阵,逐行二分查找是一种有效的优化策略。

关注窝,每三天至少更新一篇优质c语言题目详解~

[专栏链接QwQ] :⌈c语言日寄⌋CSDN
[关注博主ava]:siy2333
感谢观看~ 我们下次再见!!

相关文章:

[c语言日寄]在不完全递增序中查找特定要素

【作者主页】siy2333 【专栏介绍】⌈c语言日寄⌋&#xff1a;这是一个专注于C语言刷题的专栏&#xff0c;精选题目&#xff0c;搭配详细题解、拓展算法。从基础语法到复杂算法&#xff0c;题目涉及的知识点全面覆盖&#xff0c;助力你系统提升。无论你是初学者&#xff0c;还是…...

Golang的多团队协作编程模式与实践经验

Golang的多团队协作编程模式与实践经验 一、多团队协作编程模式概述 在软件开发领域&#xff0c;多团队协作编程是一种常见的工作模式。特别是对于大型项目来说&#xff0c;不同团队间需要协同合作&#xff0c;共同完成复杂的任务。Golang作为一种高效、并发性强的编程语言&…...

cv2.Sobel

1. Sobel 算子简介 Sobel 算子是一种 边缘检测算子&#xff0c;通过对图像做梯度计算&#xff0c;可以突出边缘。 Sobel X 方向卷积核&#xff1a; 用于计算 水平方向&#xff08;x 方向&#xff09; 的梯度。 2. 输入图像示例 假设我们有一个 55 的灰度图像&#xff0c;像素…...

Windows软件自动化利器:pywinauto python

Pywinauto WindowsAPP UI自动化 Windows软件自动化利器&#xff1a;pywinauto python...

关于 IoT DC3 中驱动(Driver)的理解

在开源IoT DC3物联网系统中&#xff0c;驱动&#xff08;Driver&#xff09;扮演着至关重要的角色&#xff0c;它充当了软件系统与物理设备之间的桥梁。驱动的主要功能是依据特定的通信协议连接到设备&#xff0c;并根据设备模板中配置的位号信息进行数据采集和指令控制。不同的…...

LogicFlow自定义节点:矩形、HTML(vue3)

效果&#xff1a; LogicFlow 内部是基于MVVM模式进行开发的&#xff0c;分别使用preact和mobx来处理 view 和 model&#xff0c;所以当我们自定义节点的时候&#xff0c;需要为这个节点定义view和model。 参考官方文档&#xff1a;节点 | LogicFlow 1、自定义矩形节点 custo…...

多模态本地部署ConVideoX-5B模型文生视频

文章目录 一、多模态概念1.多模态学习2. 人机交互3. 健康医疗4. 内容创作和娱乐 二、模型介绍三、环境安装1. 安装工具包2. 模型下载 四、运行代码五、代码解析六、效果生成七. 总结1. 模型介绍2. 部署环境3. 部署步骤4. 生成视频5. 应用场景 一、多模态概念 多模态&#xff0…...

html 点击弹出视频弹窗

一、效果: 点击视频按钮后,弹出弹窗 播放视频 二、代码 <div class="index_change_video" data-video-src="</...

业务干挂数据库,Oracle内存分配不足

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 作者&#xff1a;IT邦德 中国DBA联盟(ACDU)成员&#xff0c;10余年DBA工作经验 Oracle、PostgreSQL ACE CSDN博客专家及B站知名UP主&#xff0c;全网粉丝10万 擅长主流Oracle、MySQL、PG、高斯…...

MongoDB 7 分片副本集升级方案详解(下)

#作者&#xff1a;任少近 文章目录 1.4 分片升级1.5 升级shard11.6 升级shard2,shard31.7 升级mongos1.8重新启用负载均衡器1.9 推荐MongoDB Compass来验证数据 2 注意事项&#xff1a; 1.4 分片升级 使用“滚动”升级从 MongoDB 7.0 升级到 8.0&#xff0c;即在其他成员可用…...

Webpack相关优化总结

在使用webpack时提供了各种配置&#xff0c;这里结合在业务中常用的配置汇总一下可以进行的一系列的webpack优化 缩小文件搜索范围 其原理是在构建时&#xff0c;会以用户配置的Entry为开始依次递归遍历每个Module&#xff0c;在遍历每个Module时会调用相应合适的Loader对原模…...

ollama实践笔记

目录 一、linux安装文件命令&#xff1a; 二、启动ollama 三、linux 如何把ollama serve做为服务方式启动 四、安装deepseek-r1 五、如何在网页中使用ollama&#xff1f; ‌5.1 安装Open WebUI【不推荐】 5.2 安装ollama-webui-lite 六、Ubuntu安装docker、只需要一句话…...

springCloud-2021.0.9 之 服务调服务 示例

文章目录 前言springCloud-2021.0.9 之 服务调服务 示例1. 主要用到的组件2. 效果3. 源码3.1. 服务A3.2. 服务B接受接口 前言 如果您觉得有用的话&#xff0c;记得给博主点个赞&#xff0c;评论&#xff0c;收藏一键三连啊&#xff0c;写作不易啊^ _ ^。   而且听说点赞的人每…...

如何使用DHTMLX Scheduler的拖放功能,在 JS 日程安排日历中创建一组相同的事件

DHTMLX Scheduler 是一个全面的调度解决方案&#xff0c;涵盖了与规划事件相关的广泛需求。假设您在我们的 Scheduler 文档中找不到任何功能&#xff0c;并且希望在我们的 Scheduler 文档中看到您的项目。在这种情况下&#xff0c;很可能可以使用自定义解决方案来实现此类功能。…...

QxOrm生成json

下载Qxorm-1.5版本 使用vs打开项目&#xff0c;直接生成即可&#xff1a; lib目录中会生成dll和lib文件 新建Qt项目使用Qxorm: 将QxOrm中上面三个目录拷贝到新建的Qt项目中 pro文件添加使用QxOrm第三方库 INCLUDEPATH $$PWD/include/ LIBS -L"$$PWD/lib" LIBS…...

XS9922B(CHIPUP) 模拟高清 寄存器手册 XS9922B 四通道 多合一模拟高清解码芯片

XS9922B 是一款 4 通道模拟复合视频解码芯片&#xff0c;支持 HDCCTV 高清协议和 CVBS 标 清协议&#xff0c;视频制式支持 720P/1080P 高清制式和 960H/D1 标清制式。芯片将接收到的高清 模拟复合视频信号经过模数转化&#xff0c;视频解码以及 2D 图像处理之后…...

Django创建超管用户

在 Django 中创建超级用户&#xff08;superuser&#xff09;可以通过命令行工具 createsuperuser 完成。以下是具体步骤&#xff1a; 1. 确保已进行数据库迁移 在创建超级用户前&#xff0c;确保已执行数据库迁移&#xff1a; python manage.py migrate 2. 创建超级用户 …...

基于Kotlin中Flow扩展重试方法

最近项目中统一采用Kotlin的Flow来重构了网络请求相关代码。 目前的场景是&#xff0c;接口在请求的时候需要一个accessToken值&#xff0c;因为此值会过期或者不存在&#xff0c;需要刷新&#xff0c;因此最终方案是在使用Flow请求的时候先获取accessToken值然后再进行接口请求…...

好好说话:深度学习扫盲

大创项目是和目标检测算法YOLO相关的&#xff0c;浅浅了解了一些有关深度学习的知识。在这里根据本人的理解做一些梳理。 深度学习是什么&#xff1f; 之前经常听到AI&#xff0c;机器学习&#xff0c;深度学习这三个概念&#xff0c;但是对于三者的区别一直很模糊。 AI&…...

【状态空间方程】对于状态空间方程矩阵D≠0时的状态反馈与滑模控制

又到新的一年啦&#xff0c;2025新年快乐~。前几个月都没更新&#xff0c;主要还是因为不能把项目上的私密工作写进去&#xff0c;所以暂时没啥可写的。最近在山里实习&#xff0c;突然想起年前遗留了个问题一直没解决&#xff0c;没想到这两天在deepseek的加持下很快解决了&am…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...