AB103-顺序表去重¶

切片为AB38

+哈希表（仅适用于数值范围有限）

代码实现¶

C
/**
 * 顺序表去重 - 删除所有重复元素，仅保留第一个
 * @param L 指向顺序表的指针
 */
void del(Sqlist *L) {
    // 外层循环：遍历每个元素作为比较基准
    for (int i = 0; i < L->length; i++) {
        int k = i + 1;  // k指向下一个不重复元素应存放的位置

        // 内层循环：检查后续所有元素
        for (int j = i + 1; j < L->length; j++) {
            // 如果当前元素与基准元素不相等，则保留
            if (L->data[j] != L->data[i]) {
                L->data[k++] = L->data[j];
            }
            // 如果相等，则跳过（相当于删除）
        }

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

算法执行过程图解¶

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

Text Only

初始状态: [1, 2, 2, 3, 2, 3, 4] length=7

第1轮(i=0): 以1为基准
检查: 2≠1→保留, 2≠1→保留, 3≠1→保留, 2≠1→保留, 3≠1→保留, 4≠1→保留
结果: [1, 2, 2, 3, 2, 3, 4] length=7

第2轮(i=1): 以2为基准
检查: 2=2→跳过, 3≠2→保留, 2=2→跳过, 3≠2→保留, 4≠2→保留
结果: [1, 2, 3, 3, 4, 3, 4] length=5

第3轮(i=2): 以3为基准
检查: 3=3→跳过, 4≠3→保留
结果: [1, 2, 3, 4, 4, 3, 4] length=4

第4轮(i=3): 以4为基准
检查: 4=4→跳过
结果: [1, 2, 3, 4, 4, 3, 4] length=4

最终结果: [1, 2, 3, 4]

更高效的实现方式¶

方法1：单次遍历去重（有序表）¶

C
/**
 * 优化的去重算法 - 单次遍历
 * 时间复杂度：O(n)，空间复杂度：O(1)
 */
void delOptimized(Sqlist *L) {
    if (L->length <= 1) return;  // 空表或单元素表无需处理

    int writeIndex = 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;  // 更新长度
}

方法2：使用哈希表（适用于无序表）¶

用空间换时间

C
/**
 * 使用哈希表去重 - 适用于无序表
 * 时间复杂度：O(n)，空间复杂度：O(n)
 */
void delWithHash(Sqlist *L) {
    if (L->length <= 1) return;

    // 简单哈希表实现（假设元素范围有限）
    bool hash[1000] = {false};  // 根据实际数据范围调整大小
    int writeIndex = 0;

    for (int readIndex = 0; readIndex < L->length; readIndex++) {
        // 如果元素未出现过，则保留
        if (!hash[L->data[readIndex]]) {
            hash[L->data[readIndex]] = true;
            L->data[writeIndex++] = L->data[readIndex];
        }
    }

    L->length = writeIndex;
}

方法3：先排序再去重¶

C
/**
 * 先排序再去重 - 适用于可以改变元素顺序的情况
 */
void delWithSort(Sqlist *L) {
    if (L->length <= 1) return;

    // 先排序（使用快速排序等）
    QuickSort(L->data, 0, L->length - 1);

    // 再去重
    delOptimized(L);
}

复杂度分析¶

原始算法复杂度¶

时间复杂度：O(n²)¶

详细分析：

外层循环：执行 n 次
内层循环：
第1轮：比较 n-1 次
第2轮：比较 n-2 次
...
第n轮：比较 0 次
总比较次数：
Text Only
1
(n-1) + (n-2) + ... + 1 = n(n-1)/2
时间复杂度：O(n²)

空间复杂度：O(1)¶

只使用了常数个额外变量
原地操作，空间复杂度为 O(1)

优化算法复杂度¶

时间复杂度：O(n)¶

只需要一次遍历
每个元素只访问一次
时间复杂度为 O(n)

空间复杂度：O(1)¶

仍为原地操作
空间复杂度为 O(1)

关键知识点延伸¶

1. 算法思想对比¶

方法	时间复杂度	空间复杂度	适用场景
原始方法	O(n²)	O(1)	保持原顺序
单次遍历	O(n)	O(1)	保持原顺序
哈希表	O(n)	O(n)	无序表
排序去重	O(n log n)	O(1)	可改变顺序

2. 稳定性分析¶

原始算法：保持相对顺序，稳定
优化算法：保持相对顺序，稳定
哈希表方法：可能改变顺序，不稳定
排序方法：改变顺序，不稳定

3. 边界情况处理¶

C
/**
 * 完善的边界处理
 */
void delComplete(Sqlist *L) {
    // 空表或单元素表
    if (L == NULL || L->length <= 1) {
        return;
    }

    // 长度检查
    if (L->length > MAXSIZE) {
        return;  // 防止越界
    }

    int writeIndex = 1;

    for (int readIndex = 1; readIndex < L->length; readIndex++) {
        // 边界检查
        if (readIndex >= MAXSIZE || writeIndex >= MAXSIZE) {
            break;
        }

        if (L->data[readIndex] != L->data[writeIndex - 1]) {
            L->data[writeIndex++] = L->data[readIndex];
        }
    }

    L->length = writeIndex;
}

4. 扩展应用¶

4.1 保留最后一个重复元素¶

C
/**
 * 保留最后一个重复元素
 */
void delKeepLast(Sqlist *L) {
    if (L->length <= 1) return;

    int writeIndex = 0;

    for (int i = 0; i < L->length - 1; i++) {
        // 如果当前元素与下一个元素不同，则保留
        if (L->data[i] != L->data[i + 1]) {
            L->data[writeIndex++] = L->data[i];
        }
    }

    // 保留最后一个元素
    L->data[writeIndex++] = L->data[L->length - 1];
    L->length = writeIndex;
}

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

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;
}

5. 与链表去重的比较¶

C
/**
 * 链表去重（单链表）
 */
typedef struct ListNode {
    int data;
    struct ListNode *next;
} ListNode;

void delLinkedList(ListNode *head) {
    if (!head || !head->next) return;

    ListNode *current = head;

    while (current && current->next) {
        if (current->data == current->next->data) {
            // 删除重复节点
            ListNode *temp = current->next;
            current->next = current->next->next;
            free(temp);
        } else {
            current = current->next;
        }
    }
}

算法特点总结¶

原始算法特点：¶

保持原序：维持元素的原始相对顺序
原地操作：不需要额外存储空间
时间开销大：重复比较导致效率低下
逻辑清晰：容易理解和实现

优化算法特点：¶

高效性：时间复杂度从O(n²)优化到O(n)
稳定性：保持元素相对顺序
简洁性：代码更加简洁
实用性：更适合实际应用

记忆要点¶

原始方法：双重循环，外层固定基准，内层筛选不同元素
优化思路：利用已排序特性，单次遍历即可完成
核心思想：维护写入位置，只保留与前一个不同的元素
时间优化：从O(n²)到O(n)的巨大提升
适用前提：假设输入数组是有序的（这是优化的关键）