Icoding题解 线性表 删除重复

题干

顺序表 删除重复

编写算法，在一非递减的顺序表L中，删除所有值相等的多余元素。要求时间复杂度为O(n)，空间复杂度为O(1)。

函数原型如下：
void del_dupnum(SeqList *L)

相关定义如下：

1
2
3
4
5
struct _seqlist{
    ElemType elem[MAXSIZE];
    int last;
};
typedef struct _seqlist SeqList;

分析

  • 简要分析题干：
    这压根就不需要分析……

  • 应当注意的问题：

    1. 时间复杂度和空间复杂度的要求
    2. 删除值相等的元素，考虑到有多个数字可能会产生重复
    3. 数组是非递减的（重要！）

  • 解题思路：

    1. 分析题目易得，只能有一个循环（实际上存在有内外两层循环、但时间复杂度仍然为O(n)的情况，但是icoding的判定不太聪明，它只要看到两层循环就直接判不通过了）
    2. 同时，不能另外开辟一个数组，仅能对原本提供的数组进行操作。
    3. 数组是非递减的，换言之，只要跳过重复的数字即可，不重复的数字一一复制即可。

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void del_dupnum(SeqList *L) {
    //PrevIndex与NewIndex都是数组上的index
    //PrevIndex用于对原数组的探索，查看是否有重复元素
    //NewIndex顾名思义，就是我们最终获得的数组的下标
    int PrevIndex = 0;
    int NewIndex = 0;

    //遍历终止条件是，一旦指向原数组的下标到了原数组的末尾，就终止
    while (PrevIndex <= L->last) {
        //一旦相等，我们知道会有两种情况：
        //第一种情况是 PrevIndex 和 NewIndex 碰到一起
        //第二种情况是 PrevIndex和NewIndex所指的数相等
        //不管是哪种情况，我们都需要继续向后遍历，看看是不是有重复元素
        if (L->elem[PrevIndex] == L->elem[NewIndex]) {
            PrevIndex++;
        }
        //此时PrevIndex和NewIndex指向的数不相等了
        //我们知道，要把PrevIndex指向的数复制到NewIndex指向的位置
        //特别注意，PrevIndex应当是始终与NewIndex相等或更大的
        else {
            //这里NewIndex的自增原因如下：
            //我们已知两个Index指向的数字已经不相等，这种情况一般是全部跳过了重复数字
            //那么，NewIndex此时指向的数字保留
            //我们在NewIndex的下一个位置储存新的、不与前面重复的数字
            NewIndex++;
            L->elem[NewIndex] = L->elem[PrevIndex];
            PrevIndex++;
        }
    }
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void del_dupnum(SeqList *L)  {
    int prev = 0;
    int curr = 0;
    while (curr <= L->last){
        if (L->elem[curr] == L->elem[prev]){
            curr += 1;
        }
        else{
            prev += 1;
            L->elem[prev] = L->elem[curr];
            curr += 1;
        }
    }
    
    L->last = prev;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。