有序顺序表去重算法：双指针法实现与优化

1. 题目解析与需求拆解

这道题目要求我们实现一个有序顺序表的重复元素删除操作。首先需要明确几个关键概念：

• 线性表：数据结构中最基础的一种，元素之间存在一对一的前驱后继关系
• 顺序表：采用顺序存储结构实现的线性表，元素在内存中连续存放
• 有序：表中元素已按某种规则（通常为升序或降序）排列
• 删除重复元素：保留每个元素的唯一副本，去除所有重复出现的相同元素

关键点：顺序表的有序特性意味着所有重复元素必定相邻存放，这大大简化了去重算法的复杂度。

2. 算法设计与复杂度分析

2.1 暴力解法思路

最直观的做法是使用双重循环：

1. 外层循环遍历每个元素
2. 内层循环检查后续所有相同元素并删除
3. 每次删除需要移动后续所有元素

时间复杂度：O(n²)
空间复杂度：O(1)

c复制void RemoveDuplicates(SqList *L) {
    int i, j;
    for (i = 0; i < L->length; i++) {
        for (j = i + 1; j < L->length; j++) {
            if (L->data[i] == L->data[j]) {
                // 删除j位置元素
                for (int k = j; k < L->length - 1; k++) {
                    L->data[k] = L->data[k + 1];
                }
                L->length--;
                j--; // 需要重新检查当前位置
            }
        }
    }
}

2.2 优化解法（双指针法）

利用有序特性，可以采用类似合并有序链表的思想：

1. 初始化两个指针：i=0（写指针），j=1（读指针）
2. 遍历顺序表：
   • 当j位置元素≠i位置元素时，i前进一位并复制j的值
   • 否则j继续前进寻找不同元素
3. 最后调整表长为i+1

时间复杂度：O(n)
空间复杂度：O(1)

c复制void RemoveDuplicates(SqList *L) {
    if (L->length == 0) return;
    
    int i = 0;
    for (int j = 1; j < L->length; j++) {
        if (L->data[j] != L->data[i]) {
            i++;
            L->data[i] = L->data[j];
        }
    }
    L->length = i + 1;
}

3. 完整实现与测试用例

3.1 顺序表结构定义

c复制#define MAXSIZE 100  // 顺序表最大容量

typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

3.2 测试用例设计

需要考虑的边界情况：

1. 空表
2. 无重复元素
3. 全部元素相同
4. 常规有重复情况
5. 超大容量测试

c复制void TestRemoveDuplicates() {
    // 测试用例1：空表
    SqList L1 = {{}, 0};
    RemoveDuplicates(&L1);
    assert(L1.length == 0);

    // 测试用例2：无重复
    SqList L2 = {{1,2,3,4}, 4};
    RemoveDuplicates(&L2);
    assert(L2.length == 4);

    // 测试用例3：全部重复
    SqList L3 = {{5,5,5,5}, 4};
    RemoveDuplicates(&L3);
    assert(L3.length == 1 && L3.data[0] == 5);

    // 测试用例4：常规情况
    SqList L4 = {{1,2,2,3,3,3,4,5,5}, 9};
    RemoveDuplicates(&L4);
    assert(L4.length == 5);
    assert(memcmp(L4.data, (int[]){1,2,3,4,5}, 5*sizeof(int)) == 0);
}

4. 算法优化与变种问题

4.1 允许保留k个重复元素

修改算法使每个元素最多保留k个副本：

c复制void RemoveKDuplicates(SqList *L, int k) {
    if (L->length <= k) return;
    
    int i = k - 1;  // 写指针
    for (int j = k; j < L->length; j++) {
        if (L->data[j] != L->data[i - k + 1]) {
            i++;
            L->data[i] = L->data[j];
        }
    }
    L->length = i + 1;
}

4.2 无序顺序表去重

当顺序表无序时，可以采用：

1. 先排序后去重 O(nlogn)
2. 使用哈希表辅助 O(n)但需要额外空间

c复制// 方法1：排序+去重
void RemoveUnsortedDuplicates(SqList *L) {
    QuickSort(L);  // 先排序
    RemoveDuplicates(L);  // 再去重
}

// 方法2：哈希表法（伪代码）
void HashRemoveDuplicates(SqList *L) {
    HashSet set;
    int i = 0;
    for (int j = 0; j < L->length; j++) {
        if (!set.contains(L->data[j])) {
            set.insert(L->data[j]);
            L->data[i++] = L->data[j];
        }
    }
    L->length = i;
}

5. 工程实践中的注意事项

1. 边界检查：始终检查表长度是否为0
2. 元素类型：示例使用int，实际可能是任意复杂类型
3. 稳定性：保持非重复元素的原始相对顺序
4. 错误处理：处理非法输入情况
5. 性能测试：大数据量下的表现验证

实际项目中，建议添加前置条件检查：

c复制assert(L != NULL && L->length >= 0 && L->length <= MAXSIZE);

6. 复杂度对比与选择建议

在面试或考试中，遇到有序顺序表去重问题，双指针法是最优解。我曾在一个数据预处理模块中使用这种算法，将处理千万级有序数据的时间从分钟级降低到秒级。