AC108-合并两个递增有序表¶

实现代码¶

C
/**
 * 合并两个递增有序顺序表为一个递增有序顺序表
 * @param A 第一个有序顺序表
 * @param B 第二个有序顺序表
 * @param C 指向合并后的顺序表的指针
 */
void merge(Sqlist A, Sqlist B, Sqlist C) {
    int i = 0, j = 0, k = 0;  // 初始化三个指针

    // 同时遍历A和B，比较元素大小，按序放入C
    while (i < A.length && j < B.length) {
        if (A.data[i] <= B.data[j]) {
            C->data[k++] = A.data[i++];  // A的元素较小，放入C
        } else {
            C->data[k++] = B.data[j++];  // B的元素较小，放入C
        }
    }

    // 如果A还有剩余元素，全部复制到C
    while (i < A.length) {
        C->data[k++] = A.data[i++];
    }

    // 如果B还有剩余元素，全部复制到C
    while (j < B.length) {
        C->data[k++] = B.data[j++];
    }

    // 设置合并后顺序表的长度
    C->length = A.length + B.length;
}

算法执行过程图解¶

假设： - A：[1, 3, 5, 7] - B：[2, 4, 6, 8] - C：初始为空

初始状态¶

Text Only
1 2 3 4 5 6	`A: [1, 3, 5, 7] ↑ B: [2, 4, 6, 8] ↑ C: [] ↑`

第一步：比较 `A[0]=1` 和 `B[0]=2`¶

1 < 2，将 1 放入 C。

Text Only
1 2 3 4 5 6	`A: [1, 3, 5, 7] ↑ B: [2, 4, 6, 8] ↑ C: [1] ↑`

第二步：比较 `A[1]=3` 和 `B[0]=2`¶

2 < 3，将 2 放入 C。

Text Only
1 2 3 4 5 6	`A: [1, 3, 5, 7] ↑ B: [2, 4, 6, 8] ↑ C: [1, 2] ↑`

第三步：继续比较¶

比较 A[1]=3 和 B[1]=4 → 放入 3。
比较 A[2]=5 和 B[1]=4 → 放入 4。
比较 A[2]=5 和 B[2]=6 → 放入 5。
比较 A[3]=7 和 B[2]=6 → 放入 6。
比较 A[3]=7 和 B[3]=8 → 放入 7。

最终状态¶

A 和 B 均已遍历完毕。
将 B[3]=8 放入 C。
Text Only
1
C: [1, 2, 3, 4, 5, 6, 7, 8]

复杂度分析¶

时间复杂度：O(M + N)¶

主循环：
每次比较后，至少有一个指针 (i 或 j) 前进。
总比较次数最多为 M + N（两个表的总长度）。
处理剩余元素：
如果一个表先遍历完，另一个表的剩余部分直接复制。
这部分操作的时间复杂度为 O(剩余元素个数)。
结论：时间复杂度为 O(M + N)。

空间复杂度：O(1)¶

额外变量：
只使用了常数个额外变量（i, j, k）。
没有使用额外的存储空间。
输出数组：
结果存储在 C 中，但这是必要的输出，不计入额外空间。
结论：空间复杂度为 O(1)。

关键知识点延伸¶

1. 算法核心思想¶

双指针技巧¶

指针 i：用于遍历表 A。
指针 j：用于遍历表 B。
指针 k：用于标记合并结果表 C 的写入位置。
利用有序性：由于 A 和 B 已排序，只需依次比较当前元素即可。

原地合并的优势¶

不需要额外的临时数组。
直接将结果写入目标数组 C。

2. 特殊情况处理¶

2.1 其中一个表为空¶

如果 A 为空，则直接将 B 的所有元素复制到 C。
如果 B 为空，则直接将 A 的所有元素复制到 C。

2.2 表中有重复元素¶

算法会保留所有重复元素，因为没有去重逻辑。
如果需要去重，可以在比较时增加判断条件。

3. 扩展应用¶

3.1 合并 K 个有序表¶

可以扩展为合并多个有序表：

C
/**
 * 合并 K 个有序顺序表为一个递增有序顺序表
 * 使用最小堆实现
 */
void mergeKLists(Sqlist lists[], int k, Sqlist *C) {
    // 构建最小堆（略）
    // 每次取出堆顶元素，加入结果表，并将对应表的下一个元素插入堆
}

3.2 合并两个链表¶

如果是链表结构，可以使用类似的方法：

C
/**
 * 合并两个递增有序链表为一个递增有序链表
 */
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);  // 虚拟头节点
    ListNode* tail = &dummy;

    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    tail->next = l1 ? l1 : l2;  // 连接剩余部分
    return dummy.next;
}

4. 与归并排序的关系¶

该算法是归并排序的核心步骤之一： - 归并排序通过递归将数组分解为单个元素的子数组。 - 在合并阶段，使用类似的双指针方法将两个有序子数组合并为一个有序数组。

算法特点总结¶

高效性：时间复杂度 O(M + N)，空间复杂度 O(1)。
稳定性：保持元素的相对顺序。
简洁性：实现简单，逻辑清晰。
通用性：可用于链表、数组等多种数据结构。
可扩展性：可以扩展到合并多个有序表。

记忆要点¶

双指针技巧：i 遍历 A，j 遍历 B，k 写入 C。
核心思想：利用有序性，每次取较小的元素放入结果表。
边界处理：注意其中一个表遍历完后，直接复制另一个表的剩余部分。
时间效率：线性时间 O(M + N)，优于无序表合并的 O((M + N) log (M + N))。
空间效率：原地操作，空间复杂度 O(1)。