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



目录

一、题目详情：

二、解题代码：

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

四、算法：

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

输入格式:

        第一行输入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

思路：

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

具体思路如下：

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

代码流程解读：

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

时间和空间复杂度：

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

示例解读：

对于输入：

4

1 3 5 7

2

2 4

执行步骤：

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

        在这道里使用一个合并函数，功能是将两个顺序表合并起来，第一个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剩下的元素。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/43821.html