2025年合并两个有序数组并去重（合并两个有序数组pta）

大家好，我是讯享网，很高兴认识大家。

 <p id="main-toc"><strong>目录</strong></p>

讯享网

一、题目详情：

二、解题代码：

三、解题详细思路及代码解释：

四、算法：

请设计一个能够将有序顺序表LA，LB进行合并的算法，要求合并后的顺序表LC依然有序。

        例如：
        LA的元素 1 3 5 7
        LB的元素 2 4
        LC的元素 1 2 3 4 5 7
        其中，LA和LB的长度不超过1000，当中的元素为非递减排序。

输入格式:

第一行输入LA的长度

第二行输入LA的元素

第三行输入LB的长度

第四行输入LB的元素

输出格式:

输入合并后顺序表中各元素的值，值之间用一个空格间隔。

输入样例1:

4

1 3 5 7

2

2 4

讯享网

输出样例1:

1 2 3 4 5 7

输入样例2:

6

1 2 3 4 5 6

3

7 8 9

输出样例2:

1 2 3 4 5 6 7 8 9

讯享网

思路：

题目要求将两个有序顺序表和合并成一个有序顺序表，且合并后中的元素依旧按非递减顺序排列。考虑到和本身已经是有序的，因此可以使用 双指针法 实现线性时间复杂度的合并算法。

具体思路如下：

使用双指针：设两个指针和，分别指向和的起始元素；同时设一个指针指向合并数组的起始位置。
比较插入：比较和：
- 如果较小，则将其加入到中，并移动指针和。
- 否则，将插入中，然后移动指针和。
处理剩余元素：在其中一个数组遍历完成后，直接将另一个数组的剩余元素加入中。
输出结果：将中的元素输出，确保按题目要求格式化输出。

代码流程解读：

输入部分：
- 函数用于输入和的长度和元素，将它们分别存储在数组和中。
合并函数 ：
- 利用双指针法遍历和，依次将较小的元素放入中。
- 当一个数组的元素全部处理完毕时，直接将另一个数组的剩余元素添加到中，这样可以避免不必要的比较。
输出部分：
遍历合并后的数组，按顺序输出每个元素。使用条件判断避免在最后一个元素后输出空格。

时间和空间复杂度：

时间复杂度：该算法的时间复杂度为 O(n+m)，因为每个元素只会被处理一次。
空间复杂度：空间复杂度为 O(n+m)，因为需要一个新的数组来存储合并结果。

示例解读：

对于输入：

4

1 3 5 7

2

2 4

执行步骤：

初始化指针 , , 。
比较和，将放入，和分别加 1。
继续比较，将放入，和分别加 1。
依次比较并放入 , , , 。
输出：

在这道里使用一个合并函数，功能是将两个顺序表合并起来，第一个while直到有一个顺序表的元素数量达到极限后停止，此时，短长度的顺序表所有值与长顺序表的短长度的值所对应的元素已经全部排列完全，剩下的是长顺序表剩下的值，此时直接放里面就是拍好的，因为给的就是有顺序的表。

举个例子（范围内）：

1 3 5 7 9

2 4

在这里，短表的值包括在长表的范围内，先把长表第一个1放里面，然后j++，短表没用到，下一次才把2放里面，所以经第一次while后，短表用光了，此时

顺序为：

1 2 3 4

j=m了，不再满足第一个while的条件，进入下一个while，把长表剩下的直接放里面，为：

1 2 3 4 （5 7 9）

符合小到大顺序的是。

范围外：

1 3 5 7 9

8 11 34

这个的话情况是相同的，虽然下边是短表，但是一直用不到，所以第一个while把LA用光和用了LB的第一个元素，然后进入下一个while，放入LB剩下的元素。