AC109-合并两个递增有序表为一个递减有序表

实现代码

/**
 * 合并两个递增有序表为一个递减有序表
 * @param A 第一个递增有序表
 * @param B 第二个递增有序表
 * @param C 合并后的递减有序表（输出）
 */
void merge(Sqlist A, Sqlist B, Sqlist *C) {
    int i = A.length - 1;  // 指向A的最后一个元素（从后向前遍历）
    int j = B.length - 1;  // 指向B的最后一个元素（从后向前遍历）
    int k = 0;             // 指向C的第一个位置（从前向后填充）

    // 主循环：比较A和B的当前最大元素，选择较大的放入C
    while (i >= 0 && j >= 0) {
        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中剩余的元素
    while (i >= 0) {
        C->data[k++] = A.data[i--];
    }

    // 处理B中剩余的元素
    while (j >= 0) {
        C->data[k++] = B.data[j--];
    }

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

---

算法执行过程图解

假设： - 表 A = [1, 3, 5, 7]，长度为 4； - 表 B = [2, 4, 6, 8, 10]，长度为 5。

目标是将 A 和 B 合并为一个递减有序表 C。

初始状态

A: [1, 3, 5, 7]
             ↑
           i=3

B: [2, 4, 6, 8, 10]
                ↑
              j=4

C: []
   ↑
   k=0

第一步：比较 A[3] = 7 和 B[4] = 10

• 7 < 10，将 10 放入 C。

  C: [10]
        ↑
        k=1
  

  更新 j = 3。

第二步：比较 A[3] = 7 和 B[3] = 8

• 7 < 8，将 8 放入 C。

  C: [10, 8]
           ↑
           k=2
  

  更新 j = 2。

第三步：比较 A[3] = 7 和 B[2] = 6

• 7 > 6，将 7 放入 C。

  C: [10, 8, 7]
              ↑
              k=3
  

  更新 i = 2。

第四步：继续处理剩余元素

依次比较并插入： - A[2] = 5 vs B[2] = 6 → 插入 6； - A[2] = 5 vs B[1] = 4 → 插入 5； - A[1] = 3 vs B[1] = 4 → 插入 4； - A[1] = 3 vs B[0] = 2 → 插入 3； - A[0] = 1 vs B[0] = 2 → 插入 2； - 最后插入 A[0] = 1。

最终结果：

C: [10, 8, 7, 6, 5, 4, 3, 2, 1]

---

复杂度分析

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

1. 主循环：
2. 每次比较 A[i] 和 B[j]，选择较大的放入 C。
3. 每次操作后，i 或 j 减少 1。

4. 总共最多进行 M + N 次比较。

5. 剩余元素处理：

6. 如果 A 或 B 中还有剩余元素，则直接复制到 C。

7. 最多需要 M 或 N 次操作。

8. 总时间复杂度：O(M + N)。

---

空间复杂度：O(1)

1. 额外变量：
2. 使用了常数个额外变量（i, j, k）。

3. 没有使用额外的存储空间。

4. 原地操作：

5. 直接在 C 中存储结果。

6. 总空间复杂度：O(1)。

---

关键知识点延伸

1. 算法核心思想

双指针技巧

• 逆序遍历：从 A 和 B 的末尾开始，确保每次插入的是当前的最大值。
• 贪心策略：每次选择较大的元素放入 C，保证结果递减有序。

原地修改的优势

• 不需要额外的数组或数据结构。
• 直接在 C 中按顺序存储结果。

---

2. 特殊情况处理

2.1 空表处理

if (A.length == 0 && B.length == 0) {
    C->length = 0;
    return;
}

- 如果两个输入表都为空，则输出表也为空。

2.2 一个表为空

// 输入:
A = [], B = [2, 4, 6]
// 输出:
C = [6, 4, 2]

- 如果其中一个表为空，则直接将另一个表逆序复制到 C。

---

3. 扩展应用

3.1 合并为递增有序表

如果要求合并为递增有序表，只需调整遍历方向：

void mergeIncreasing(Sqlist A, Sqlist B, Sqlist *C) {
    int i = 0, j = 0, k = 0;

    while (i < A.length && j < B.length) {
        if (A.data[i] < B.data[j]) {
            C->data[k++] = A.data[i++];
        } else {
            C->data[k++] = B.data[j++];
        }
    }

    while (i < A.length) {
        C->data[k++] = A.data[i++];
    }

    while (j < B.length) {
        C->data[k++] = B.data[j++];
    }

    C->length = A.length + B.length;
}

3.2 归并排序的核心

该算法实际上是归并排序中“合并”步骤的一个变种。在归并排序中，通常合并为递增有序表，而这里改为递减有序表。

---

4. 边界条件与验证

4.1 边界条件

• 输入表为空或只有一个元素时，算法是否正确？
• 输入表长度不同时，算法是否能正确处理？

4.2 验证方法

• 测试用例包括：
• 两个空表。
• 一个空表，一个非空表。
• 两个长度相同的表。
• 两个长度不同的表。
• 表中包含重复元素的情况。

---

算法特点总结

1. 高效性：时间复杂度 O(M + N)，空间复杂度 O(1)。
2. 简洁性：实现简单，逻辑清晰。
3. 适用性：特别适合处理有序表的合并问题。
4. 扩展性：可以轻松扩展为其他形式的合并（如递增有序表）。

---

记忆要点

• 逆序遍历：从两个表的末尾开始，确保每次插入的是当前的最大值。
• 贪心策略：每次选择较大的元素放入结果表。
• 双指针技巧：分别指向两个表的当前处理位置。
• 边界处理：注意空表和剩余元素的处理。
• 时间效率：线性时间 O(M + N)，空间复杂度 O(1)。