2.2 综合题：在顺序表上原地去重与合并

综合题的难点是同时维护“读到哪里”和“有效区多长”。典型任务：删除有序顺序表中的重复值。因为相同元素相邻，可用一个指针扫描、一个指针记录最后一个不同元素：

int unique_sorted(int a[], int n) {
    if (n == 0) return 0;
    int k = 0;
    for (int i=1; i<n; ++i)
        if (a[i] != a[k]) a[++k] = a[i];
    return k + 1;
}

循环不变量是：每轮开始时 a[0..k] 已是原前缀去重后的结果，且 a[k] 是最后一个保留值。遇到新值先增 k 再写入。时间 $O(n)$、额外空间 $O(1)$。

若表无序，上述相邻比较会漏掉不相邻重复项。可以对每个元素检查已保留区，时间 $O(n^2)$；也可借助哈希集合换取平均 $O(n)$ 时间，但额外空间变为 $O(n)$。题目若明确“原地”或“不准改变相对次序”，方案选择会不同。

再看两个有序表合并。设置 i,j,k，每次把两表当前较小值写入结果，某一表耗尽后复制另一表剩余部分。比较次数至多 $m+n-1$，写入 $m+n$ 次，总时间 $O(m+n)$、结果空间 $O(m+n)$。若要求把两个升序段原地合并，不能直接覆盖尚未读取的数据，通常要从尾部向前填充，或付出元素移动成本。

错解反馈：循环中删除一个元素后仍无条件 i++，会跳过左移过来的新元素；只写代码不说明有序前提，算法正确性范围不清；声称原地合并额外空间 $O(1)$，却偷偷创建长度 $m+n$ 的数组，空间分析不诚实。

迁移练习：对有序数组 [1,1,2,2,2,5] 写出每轮 (i,k) 与有效前缀，最终新长度为 3、前缀为 [1,2,5]。独立验收：能陈述循环不变量，并给空表、全重复、无重复三组边界测试。