PTA（顺序表）2-8 合并有序数组

2-8 合并有序数组

分数 7

作者 伍建全

单位 重庆科技大学

给定2个非降序序列，要求把他们合并成1个非降序序列。假设所有元素个数为N，要求算法的时间复杂度为O(N)。

输入格式:

输入有4行。
第1行是一个正整数m，表示第2行有m个整数，这些整数构成一个非降序序列，每个整数之间以空格隔开。第3行是一个正整数n，表示第4行有n个整数，这些整数也构成一个非降序序列，每个整数之间以空格隔开。

输出格式:

把第2行的m个整数和第4行的n个整数合并成一个非降序序列，输出这个整数序列。每个数之间隔1个空格。

输入样例:

6
1 3 6 6 8 9  
4
2 4 5 7

输出样例:

1 2 3 4 5 6 6 7 8 9 

答案

#include <iostream>
using namespace std;

// 定义顺序表结构
typedef struct {
    int *data;
    int length;
} sqList;

// 初始化顺序表
void initList(sqList &L, int n) {
    L.data = new int[n];
    L.length = 0;
}

// 将元素x插入到顺序表尾部
void insertElem(sqList &L, int x) {
    L.data[L.length] = x;
    L.length++;
}

// 将两个表合并
void combineList(sqList &L, sqList L1, sqList L2) {
    int i = 0;
    int j = 0;
    while (i != L1.length && j != L2.length) {
        if (L1.data[i] <= L2.data[j]) { // L1当前小，先插入新表
            insertElem(L, L1.data[i]);
            i++;
        } else if (L1.data[i] > L2.data[j]) { // L2当前小，先插入新表
            insertElem(L, L2.data[j]);
            j++;
        }
    }
    // 当L1先读取完，把L2剩余的移到新表中
    while (j != L2.length) {
        insertElem(L, L2.data[j]);
        j++;
    }
    // 当L2先读取完，把L1剩余的移到新表中
    while (i != L1.length) {
        insertElem(L, L1.data[i]);
        i++;
    }
}

int main() {
    int m, n;

    cin >> m; // 先读取第一个顺序表的元素个数
    sqList L1;
    initList(L1, m);
    // 将元素填入表1
    for (int i = 0; i < m; ++i) {
        cin >> L1.data[i];
        L1.length++;
    }

    cin >> n; // 读取第二个顺序表的元素个数
    sqList L2;
    initList(L2, n);
    // 将元素填入表2
    for (int i = 0; i < n; ++i) {
        cin >> L2.data[i];
        L2.length++;
    }

    // 合并两个顺序表到一个新顺序表中
    sqList L;
    initList(L, m+n);
    combineList(L, L1, L2);

    // 输出合并之后的表
    for (int i = 0; i < L.length; ++i) {
//        if (i != 0) {
//            cout << " ";
//        }
        cout << L.data[i] << " ";
    }
}

归并（Merge）操作，基于**双指针（Two Pointers）**技术。

1. 数据结构选择： 您使用了基于动态数组的 sqList (顺序表) 来存储序列，这对于顺序访问和 O(1) 插入尾部非常高效。
2. 核心算法 combineList：
   • 双指针： 您维护了两个指针 i 和 j，分别指向两个输入序列 L1 和 L2 的当前未处理元素。
   • 比较与选择： 在 while 循环中，您不断比较 L1.data[i] 和 L2.data[j]，将较小的那个元素插入到结果序列 L 中。这保证了 L 始终保持非降序。
   • 时间复杂度 O(N)： 每次比较都会将一个元素移动到最终序列中，因此总共的比较和移动次数是 m+n=N，达到了题目要求的 O(N) 时间复杂度。
3. 处理剩余元素： 在一个序列被完全遍历后，您使用了两个独立的 while 循环将另一个序列中剩余的所有元素（它们本身已经有序）直接复制到结果序列 L 的末尾。