Icoding题解 线性表 删除指定范围

题干

顺序表 删除指定范围

设计一个高效的算法，从顺序表L中删除所有值介于x和y之间(包括x和y)的所有元素（假设y>=x），要求时间复杂度为O(n)，空间复杂度为O(1)。

函数原型如下：
void del_x2y(SeqList *L, ElemType x, ElemType y)

相关定义如下：

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

分析

  • 简要分析题干：
    这压根就不需要分析……它比链表那道题更加简单直接

  • 应当注意的问题：

    1. 时间复杂度和空间复杂度的要求
    2. 删除大于等于x小于等于y的数字
    3. 对单个数组的操作

  • 解题思路：

    1. 用两个index即可完成。
    2. 一个index一旦检测到了小于x或大于y的数字，就将其指向的值赋值给另一个index指向的位置，另一个index自增。

核心代码

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
void del_x2y(SeqList *L, ElemType x, ElemType y) {
    int NewIndex = 0;
    int CurrIndex = 0;
    int flag = 0;
    //遍历到末尾为止
    while (CurrIndex <= L->last) {
        //判断：如果数字大于y，或者是小于x，就是我们不需要删除的数字
        if (L->elem[CurrIndex] < x || L->elem[CurrIndex] > y) {
            //将数字赋值给NewIndex指向的位置
            L->elem[NewIndex] = L->elem[CurrIndex];
            //NewIndex指向下一个位置
            NewIndex++;
            flag = 1;
        }
        //不论任何情况，CurrIndex在每次循环都需要自增
        CurrIndex++;
    }
    //不要忘记更新数组的最后下标的位置
    //减去1的原因很简单，在最后一次更新时，我们使NewIndex++了
    if (flag) {
        L->last = NewIndex - 1;
    }
    else {
        L->last = NewIndex;
    }
}

完整代码

完整代码和前面带注释的版本又有不同哦，完整代码的版本的水平其实是比较差的，不过两者运用的思想其实完全一致，读者不妨看看下面的代码究竟差在哪里？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void del_x2y(SeqList *L, ElemType x, ElemType y) {
    int position = 0;
    int judge = 0;
    ElemType temp = 0;
    while(judge <= L->last){
        if(L->elem[judge] < x || L->elem[judge] > y){
            temp = L->elem[position];
            L->elem[position] = L->elem[judge];
            L->elem[judge] = temp;
            position++;
            judge++;
        }
        else{
            judge++;
        }
    }
    L->last = position - 1;
}
许可协议

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