PTA： 有序顺序表的合并

请设计一个能够将有序顺序表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 

代码 

#include <stdio.h>

int main() {
    int n, m;
    int LA[1000], LB[1000], LC[2000];
    
    // 读取LA
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &LA[i]);
    }
    
    // 读取LB
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &LB[i]);
    }
    
    // 合并
    int i = 0, j = 0, k = 0;
    while (i < n && j < m) {
        if (LA[i] <= LB[j]) {
            LC[k++] = LA[i++];
        } else {
            LC[k++] = LB[j++];
        }
    }
    // 处理剩余元素
    while (i < n) {
        LC[k++] = LA[i++];
    }
    while (j < m) {
        LC[k++] = LB[j++];
    }
    
    // 输出
    if (k > 0) {
        for (int idx = 1; idx < k; idx++) {
            printf("%d ", LC[idx]);
        }
    }
    printf("\n");
    
    return 0;
}

算法思路

1. 输入处理：分别读取两个有序顺序表LA和LB。
2. 归并合并：
   • 使用双指针法，比较两表的当前元素，将较小的元素加入新表LC。
   • 当某一表遍历完后，将另一表剩余元素直接追加到LC。
3. 输出结果：确保元素间以空格分隔，末尾无多余空格。

核心逻辑

• 时间复杂度：O(n + m)，仅需一次遍历即可完成合并。
• 空间复杂度：O(n + m)，存储合并后的结果。

关键点

• 双指针归并：利用有序特性，通过一次遍历完成高效合并。
• 边界处理：正确处理输入表的剩余元素。
• 输出格式：通过条件判断确保输出格式正确。