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

顺序表-递增有序表合并

两个递增有序表合并操作

题目:

将两个递增有序的顺序表 AB 合并成一个新的递增有序顺序表 C

思路:

  1. 使用三个索引 i, j, k 分别遍历顺序表 A, B 和合并后的顺序表 C
  2. 比较 AB 当前索引指向的元素,将较小的元素放入 C 中,并移动对应的索引。
  3. AB 的元素全部放入 C 后,将剩余的元素直接复制到 C 中。

整体代码:

// 函数声明,用于合并两个递增有序顺序表A和B到顺序表C中
bool merge(Sqlist A, Sqlist B, Sqlist &C) {int i = 0, j = 0, k = 0; // 初始化索引i, j, k为0,分别用于A, B和C// 合并两个有序表的元素到C中while (i < A.length && j < B.length) { // 当A和B都还有元素时if (A.data[i] < B.data[j]) { // 如果A的当前元素小于B的当前元素C.data[k++] = A.data[i++]; // 将A的元素放入C,并移动A和C的索引} else {C.data[k++] = B.data[j++]; // 将B的元素放入C,并移动B和C的索引}}// 将A中剩余的元素复制到C中while (i < A.length) {C.data[k++] = A.data[i++];}// 将B中剩余的元素复制到C中while (j < B.length) {C.data[k++] = B.data[j++];}C.length = k; // 更新C的长度为合并后的元素数量return true; // 返回成功标志
}

题目:

尽可能高效找出数组中未出现的最小正整数。

思路:

  1. 初始化辅助数组:创建一个大小为 n 的辅助数组 B,用于标记数组 A 中出现的正整数。
  2. 标记出现的正整数:遍历数组 A,对于每个正整数 A[i],如果 A[i]1n 之间,则将 B[A[i] - 1] 标记为 1
  3. 查找未出现的最小正整数:再次遍历辅助数组 B,找到第一个值为 0 的位置,该位置即为未出现的最小正整数。
  4. 释放辅助数组:删除辅助数组 B

整体代码:

int find(int A[], int n) {// 1. 初始化辅助数组 B,大小为 nint *B = new int[n]; // 创建大小为 n 的辅助数组 B// 2. 遍历数组 A,标记出现的正整数for (int k = 0; k < n; ++k) {B[k] = 0; // 初始化 B 数组,标记未出现的正整数}for (int i = 0; i < n; ++i) {if (A[i] > 0 && A[i] <= n) {B[A[i] - 1] = 1; // 标记 A[i] 出现,B[A[i] - 1] 为 1}}// 3. 查找未出现的最小正整数for (int i = 0; i < n; ++i) {if (B[i] == 0) {break; // 找到第一个未出现的正整数,退出循环}}// 4. 释放辅助数组 Bdelete[] B; // 释放辅助数组 B 的内存// 返回未出现的最小正整数return i + 1; // 返回未出现的最小正整数
}

说明:

  • 辅助数组 B:用于标记数组 A 中出现的正整数。
  • 标记出现的正整数:遍历数组 A,对于每个正整数 A[i],如果 A[i]1n 之间,则将 B[A[i] - 1] 标记为 1
  • 查找未出现的最小正整数:再次遍历辅助数组 B,找到第一个值为 0 的位置,该位置即为未出现的最小正整数。
  • 释放辅助数组:删除辅助数组 B,释放内存。

相关文章:

顺序表-递增有序表合并

两个递增有序表合并操作 题目&#xff1a; 将两个递增有序的顺序表 A 和 B 合并成一个新的递增有序顺序表 C。 思路&#xff1a; 使用三个索引 i, j, k 分别遍历顺序表 A, B 和合并后的顺序表 C。比较 A 和 B 当前索引指向的元素&#xff0c;将较小的元素放入 C 中&#xf…...

【Qt】qt安装

在工作一年之后&#xff0c;还是想做一个Qt的教程&#xff0c;遥想研一刚刚接触Qt&#xff0c;从0到1学习&#xff0c;没有什么参考书籍&#xff0c;网上的资料也不多&#xff0c;幸好Qt官方文档写得好&#xff0c;加上自己肯研究&#xff0c;才堪堪入门。 现在我想自己写一个…...

CXF WebService SpringBoot 添加拦截器,处理响应报文格式

描述 XFIRE升级CXF框架&#xff0c;但是对接的系统不做调整&#xff0c;这时候就要保证参数报文和响应报文和以前是一致的。但是不同的框架有不同的规则&#xff0c;想要将报文调整的一致&#xff0c;就需要用到拦截器拦截报文&#xff0c;自定义解析处理。 CXF框架本身就是支…...

vue iframe进行父子页面通信并切换URL

使用通义千问提问后得到一个很好的示例。 需求是2个项目需要使用同一个面包屑进行跳转&#xff0c;其中一个是iframe所在的项目&#xff0c;另一个需要通过地址访问。通过 window.parent.postMessage &#xff0c;帮助 <iframe> 内嵌入的子页面和其父页面之间进行跨域通…...

基于Spring Boot的摄影师分享交流社区

一、系统背景与目的 随着摄影技术的不断发展和摄影爱好者群体的日益扩大&#xff0c;摄影师们需要一个能够展示自己作品、分享摄影心得、交流摄影技巧的平台。基于Spring Boot的摄影师分享交流社区应运而生&#xff0c;它旨在满足摄影师们的这些需求&#xff0c;促进摄影文化的…...

Web 毕设篇-适合小白、初级入门练手的 Spring Boot Web 毕业设计项目:电影院后台管理系统(前后端源码 + 数据库 sql 脚本)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 项目介绍 2.0 用户登录功能 3.0 用户管理功能 4.0 影院管理功能 5.0 电影管理功能 6.0 影厅管理功能 7.0 电影排片管理功能 8.0 用户评论管理功能 9.0 用户购票功…...

Linux(网络协议和管理)

后面也会持续更新&#xff0c;学到新东西会在其中补充。 建议按顺序食用&#xff0c;欢迎批评或者交流&#xff01; 缺什么东西欢迎评论&#xff01;我都会及时修改的&#xff01; 在这里真的很感谢这位老师的教学视频让迷茫的我找到了很好的学习视频 王晓春老师的个人空间…...

C++ 入门第 20 天:STL 容器之无序集合与无序多重集合

往期回顾&#xff1a; C 入门17&#xff1a;STL 容器之映射&#xff08;map&#xff09;与多重映射&#xff08;multimap&#xff09;_-CSDN博客 C 入门18&#xff1a;STL 容器之栈&#xff08;stack&#xff09;与队列&#xff08;queue&#xff09;-CSDN博客 C 入门19&#x…...

devops-部署Harbor实现私有Docker镜像仓库

文章目录 概述下载配置安装安装后生成的文件使用和维护Harbor参考资料 概述 Harbor是一个开源注册中心&#xff0c;它使用策略和基于角色的访问控制来保护工件&#xff0c;确保镜像被扫描并且没有漏洞&#xff0c;并将镜像签名为可信的。Harbor是CNCF的一个毕业项目&#xff0…...

rebase ‘A‘ onto ‘master‘ 和 merge ‘master‘ into ‘A‘有什么区别

在Git版本控制系统中&#xff0c;rebase 和 merge 是两种不同的操作&#xff0c;用于合并分支。rebase A onto master 和 merge master into A 虽然最终目的都是将两个分支的更改合并在一起&#xff0c;但它们在处理方式和结果上有所不同。 rebase ‘A’ onto ‘master’ 含义…...

Vulhub:Jackson[漏洞复现]

CVE-2017-7525(Jackson反序列化) 启动漏洞环境 docker-compose up -d 阅读vulhub给出的漏洞文档 cat README.zh-cn.md # Jackson-databind 反序列化漏洞&#xff08;CVE-2017-7525&#xff09; Jackson-databind 支持 [Polymorphic Deserialization](https://github.com/Fas…...

strongswan构建测试环境

make-testing脚本文件负责构建strongswan的虚拟化测试系统。位于目录strongswan-5.9.14/testing/&#xff0c;需要以管理员身份运行make-testing。生成测试用到的虚拟客户机镜像&#xff0c;KVM虚拟机和虚拟网络的配置文件位于目录:config/kvm。 ~/strongswan-5.9.14/testing$…...

前端:金额高精度处理

Decimal 是什么 想必大家在用js 处理 数字的 加减乘除的时候&#xff0c;或许都有遇到过 精度不够 的问题&#xff0c;还有那些经典的面试题 0.20.1 ! 0.3&#xff0c; 至于原因&#xff0c;那就是 js 计算底层用的是 IEEE 754 &#xff0c;精度上有限制&#xff0c; 那么Deci…...

面试题整理3----nc命令的常见用法

面试题整理3----nc命令的常见用法 1. NC是什么2. NC的常用参数2.1 开启指定端口TCP监听(-l小写的L)2.2 测试端口是否能访问(-v)2.3 开启指定端口UDP监听(-u)2.4 端口扫描(-z)2.5 指定超时时间(-w)2.6 指定本地端口号连接(-p)2.7 指定的命令(-e) 1. NC是什么 nc&#xff08;Net…...

Trimble天宝三维激光扫描仪在建筑工程竣工测量中的应用【沪敖3D】

竣工测量是建筑项目竣工阶段的一个至关重要的环节&#xff0c;它为建筑工程的质量验收和成果核查提供了核心的参考依据。传统的竣工测量方法&#xff0c;如全站仪测量&#xff0c;主要依赖于现场人工操作&#xff0c;存在一些明显的局限性&#xff0c;例如作业时间长、工作量大…...

IntelliJ IDEA 使用技巧与插件推荐

目录 常用使用技巧 1. 使用快捷键提升开发效率 2. 多光标编辑 3. 代码自动补全 4. 使用 Find Action 快速执行操作 5. 集成版本控制系统&#xff08;VCS&#xff09; 6. 快速查看代码文档 推荐插件 1. Lombok Plugin 2. Rainbow Brackets 3. Key Promoter X 4. Chec…...

Oracle 技术精选学习

Oracle 技术犹如一座闪耀着无尽光芒的灯塔&#xff0c;为众多 IT 从业者和技术爱好者照亮了前行的道路。无论是数据库管理、企业应用开发还是数据分析&#xff0c;Oracle 都以其强大、稳定和广泛的应用而占据着行业的重要地位。学习 Oracle 技术&#xff0c;更是能为个人带来诸…...

sqlilabs第三十关到第三十五关靶场攻略

第三十关 第三十关和二十九关差不多&#xff0c;将单引号换成双引号 查询表名&#xff0c;字段名&#xff0c;数据 ?id1&id-2" union select 1,group_concat(table_name),3 from information_schema.tables where table_schemadatabase()-- ?id1&id-2" …...

windows免登录linux

windows 生成秘钥文件 ssh-keygen -t rsa 将公钥传送到服务器 scp C:\Users\xx/.ssh/id_rsa.pub xxxx:/home/ruoyi/id_rsa.pub linux 使用ssh-copy-id -i ~/.ssh/id_rsa.pub userhost 如果禁用root登录&#xff0c;先开启 vim /etc/ssh/sshd_config PermitRootLogin yes …...

matlab绘图时设置左、右坐标轴为不同颜色

目录 一、需求描述 二、实现方法 一、需求描述 当图中存在两条曲线&#xff0c;需要对两条曲线进行分别描述时&#xff0c;应设置左、右坐标轴为不同颜色&#xff0c;并设置刻度线&#xff0c;且坐标轴颜色需要和曲线颜色相同。 二、实现方法 1.1、可以实现&#xff1a; 1…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...