主页
题目
状态
排名
OI排名
统计
题解
请登录
常用链接
AOJ考试平台
老赵的Gitee代码
编译原理模拟考试平台
Java技术手册
FCC网站
菜鸟网
在线工具箱
字节豆包GPT
代码可视化
力扣网
牛客网
洛谷
杭电OJ
CodeForce
隐藏编译器
Problem A: 算法2-2:有序线性表的有序合并
上一题
正确率: $61.19\%$
下一题
Time Limit
$1$ 秒/Second(s)
Memory Limit
$512$ 兆字节/Megabyte(s)
提交总数
$268$
正确数量
$164$
"
裁判形式
标准裁判/Standard Judge
我的状态
尚未尝试
难度
分类标签
×
为本题添加算法分类(请不要超过5个)
当前分类(单击移除):
单击选择分类:
Description
<div> 已知线性表 LA 和 LB 中的数据元素按值非递减有序排列,现要求将 LA 和 LB 归并为一个新的线性表 LC, 且 LC 中的数据元素仍然按值非递减有序排列。例如,设LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 则 </div> <div> LC=(2,3,6,6,8,8,9,11,11,15,20) </div> <div> 算法描述如下: </div> <div> 从上述问题要求可知,LC中的数据元素或是LA中的数据元素,或是LB中的数据元素,则只要先设LC为空表,然后将LA或LB中的元素逐个插入到LC中即可。为使LC中元素按值非递减有序排列,可设两个指针 i 和 j 分别指向LA和LB中某个元素,若设 i 当前所指的元素为 a,j 所指的元素为 b,则当前应插入到 LC 中的元素 c 为 c = a < b ? a : b显然,指针 i 和 j 的初值均为1(实际写代码时往往是从 0 开始的),在所指元素插入 LC 之后,在 LA 或者 LB 中顺序后移。上述归并算法如下图: </div> <div style="text-align:center;"> <img width="500" height="493" alt="" src="/JudgeOnline/admin/../upload/pimg2053_1.jpg" /> </div> <div align="center" style="text-align:center;"> <img width="0" height="0" alt="" src="/JudgeOnline/admin/../upload/pimg2053_1.jpg" /> </div> <div align="center" style="text-align:center;"> </div> <div align="center" style="text-align:center;"> 图:有序列表有序插入算法 </div>
Input
<p> <span style="font-size:10.5pt;">有多组测试数据,每组测试数据占两行。第一行是集合</span><span style="font-size:10.5pt;">A</span><span style="font-size:10.5pt;">,第一个整数</span><span style="font-size:10.5pt;">m</span><span style="font-size:10.5pt;">(</span><span style="font-size:10.5pt;">0<=m<=100</span><span style="font-size:10.5pt;">)代表集合</span><span style="font-size:10.5pt;">A</span><span style="font-size:10.5pt;">起始有</span><span style="font-size:10.5pt;">m</span><span style="font-size:10.5pt;">个元素,后面有</span><span style="font-size:10.5pt;">m</span><span style="font-size:10.5pt;">个非递减排序的整数,代表</span><span style="font-size:10.5pt;">A</span><span style="font-size:10.5pt;">中的元素。第二行是集合</span><span style="font-size:10.5pt;">B</span><span style="font-size:10.5pt;">,第一个整数</span><span style="font-size:10.5pt;">n(0<=n<=100)</span><span style="font-size:10.5pt;">代表集合</span><span style="font-size:10.5pt;">B</span><span style="font-size:10.5pt;">起始有</span><span style="font-size:10.5pt;">n</span><span style="font-size:10.5pt;">个元素,后面有</span><span style="font-size:10.5pt;">n</span><span style="font-size:10.5pt;">个非递减排序的整数,代表</span><span style="font-size:10.5pt;">B</span><span style="font-size:10.5pt;">中的元素。每行中整数之间用一个空格隔开。</span> </p>
Output
<p> <span style="font-size:10.5pt;">每组测试数据只要求输出一行,这一行含有</span><span style="font-size:10.5pt;"> m+n </span><span style="font-size:10.5pt;">个来自集合</span><span style="font-size:10.5pt;"> A </span><span style="font-size:10.5pt;">和集合</span><span style="font-size:10.5pt;">B </span><span style="font-size:10.5pt;">中的元素。结果依旧是非递减的。每个整数间用一个空格隔开。</span> </p>
Sample Input
复制
4 3 5 8 11 7 2 6 8 9 11 15 20
Sample Output
复制
2 3 5 6 8 8 9 11 11 15 20
提示
<div align="left" style="text-align:left;"> <b><span style="color:blue;"> 总结:</span></b> </div> <p> <span style="font-size:10.5pt;"> 本题书中提供的算法是基于顺序表的。在使用顺序表时需要两倍于数据元素数目。如果使用链表则只需要存储一倍的元素。然而使用链表同样需要存储一倍的指针。所以对于这类问题数据结构的选取,如果数据域占用的空间很大则可以使用链表存储来节省空间,而对于数据域占用不大的情况,则使用顺序表也可以。</span> </p> <p> <span style="font-size:14px;">多组输入</span> </p>
AOJ
Please Login