AC104-从有序表中删除所有值重复的元素，仅保留第一个¶

问题分析¶

给定一个有序顺序表，要求删除所有重复元素，仅保留每个值的第一个出现位置。目标是实现尽可能高效的算法。

已知条件：¶

输入有序性：数组已排序，重复元素必定相邻。
原地操作：不能使用额外的存储空间，只能修改原数组。
时间复杂度：尽量达到线性时间 O(n)。
空间复杂度：O(1)。

实现代码¶

C
/**
 * 从有序顺序表中删除所有重复元素，仅保留第一个
 * @param L 指向顺序表的指针
 */
void del(Sqlist *L) {
    // 边界检查：空表或单元素表无需处理
    if (L->length <= 1) return;

    int writeIndex = 1;  // 写入位置索引，初始为1（保留第一个元素）

    // 遍历顺序表中的所有元素
    for (int readIndex = 1; readIndex < L->length; readIndex++) {
        // 如果当前元素与前一个不重复元素不同，则保留
        if (L->data[readIndex] != L->data[writeIndex - 1]) {
            L->data[writeIndex++] = L->data[readIndex];  // 写入并移动写指针
        }
        // 如果相等，则跳过（相当于删除）
    }

    // 更新顺序表长度为不重复元素的个数
    L->length = writeIndex;
}

算法执行过程图解¶

假设顺序表为：[1, 2, 2, 3, 3, 3, 4, 5, 5]

初始状态¶

Text Only
1 2 3 4	`原始数组: [1, 2, 2, 3, 3, 3, 4, 5, 5] ↑ ↑ writeIndex=1 readIndex=1`

第一步：读取 `readIndex=1` 的元素 `2`¶

L->data[1] == 2，与 L->data[0] == 1 不同。

将 2 写入 writeIndex=1 的位置，并递增 writeIndex。

Text Only
1 2 3 4	`结果数组: [1, 2, 2, 3, 3, 3, 4, 5, 5] ↑ ↑ writeIndex=2 readIndex=2`

第二步：读取 `readIndex=2` 的元素 `2`¶

L->data[2] == 2，与 L->data[1] == 2 相同。
跳过此元素，writeIndex 不变。

第三步：读取 `readIndex=3` 的元素 `3`¶

L->data[3] == 3，与 L->data[1] == 2 不同。

将 3 写入 writeIndex=2 的位置，并递增 writeIndex。

Text Only
1 2 3 4	`结果数组: [1, 2, 3, 3, 3, 3, 4, 5, 5] ↑ ↑ writeIndex=3 readIndex=4`

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

同理，依次处理 3、4、5，最终得到如下结果：

Text Only
1 2 3	`结果数组: [1, 2, 3, 4, 5, 3, 4, 5, 5] ↑ writeIndex=5`

最终结果¶

将 L->length 更新为 writeIndex=5，表示有效部分为 [1, 2, 3, 4, 5]。

复杂度分析¶

时间复杂度：O(n)¶

遍历次数：
只需一次从左到右的线性扫描。
每个元素最多访问一次。
操作次数：
每次比较后，只有在需要时才进行写入操作。
总操作次数与元素数量成正比。
结论：时间复杂度为 O(n)。

空间复杂度：O(1)¶

额外变量：
使用了常数个额外变量（writeIndex 和 readIndex）。
没有使用额外的存储空间。
原地操作：
修改原数组，直接覆盖重复元素。
结论：空间复杂度为 O(1)。

关键知识点延伸¶

1. 算法核心思想¶

双指针技巧¶

读指针 (readIndex)：用于遍历整个数组。
写指针 (writeIndex)：用于标记不重复元素应该存放的位置。
利用有序性：由于数组已排序，重复元素必定相邻，只需比较相邻元素即可。

原地修改的优势¶

不需要额外的数组或数据结构。
直接在原数组上操作，节省空间。

2. 特殊情况处理¶

2.1 空表或单元素表¶

C
if (L->length <= 1) return;

- 如果顺序表为空或只有一个元素，直接返回，无需处理。

2.2 全部元素相同¶

C
1 2	`// 输入: [5, 5, 5, 5, 5] // 输出: [5]`

- 算法会正确保留第一个元素，并更新长度。

2.3 无重复元素¶

C
1 2	`// 输入: [1, 2, 3, 4, 5] // 输出: [1, 2, 3, 4, 5]`

- 算法不会修改原数组，直接返回。

3. 扩展应用¶

3.1 删除所有重复元素（包括第一个）¶

如果要求删除所有重复出现的元素，只保留唯一出现的元素：

C
void delAllDuplicates(Sqlist *L) {
    if (L->length <= 1) return;

    int writeIndex = 0;

    for (int i = 0; i < L->length; ) {
        int j = i;
        // 找到连续相同元素的结束位置
        while (j < L->length && L->data[j] == L->data[i]) {
            j++;
        }

        // 如果只有一个相同元素，则保留
        if (j - i == 1) {
            L->data[writeIndex++] = L->data[i];
        }

        i = j;  // 移动到下一个不同元素
    }

    L->length = writeIndex;
}

3.2 统计每个元素的重复次数¶

如果需要统计每个元素的重复次数：

C
void countDuplicates(Sqlist *L, int counts[]) {
    if (L->length <= 1) return;

    int current = L->data[0];
    int count = 1;

    for (int i = 1; i < L->length; i++) {
        if (L->data[i] == current) {
            count++;
        } else {
            counts[current] = count;
            current = L->data[i];
            count = 1;
        }
    }

    // 记录最后一个元素的计数
    counts[current] = count;
}

4. 与无序表去重的对比¶

特性	有序表去重	无序表去重
时间复杂度	O(n)	O(n²) 或 O(n)（使用哈希表）
空间复杂度	O(1)	O(1) 或 O(n)（使用哈希表）
保持顺序	是	视方法而定
实现难度	简单	中等

算法特点总结¶

高效性：时间复杂度 O(n)，空间复杂度 O(1)。
稳定性：保持元素的相对顺序。
简洁性：实现简单，逻辑清晰。
适用性：特别适合处理有序数据。
通用性：可以扩展到其他相关问题（如统计重复次数、删除所有重复元素等）。

记忆要点¶

双指针技巧：readIndex 遍历数组，writeIndex 标记写入位置。
核心思想：利用有序性，只需比较相邻元素。
边界处理：注意空表和单元素表的情况。
时间效率：线性时间 O(n)，优于无序表去重的 O(n²)。
空间效率：原地操作，空间复杂度 O(1)。