PTA（顺序表）1-2 数组元素的区间删除

zhangzhang2025-10-142025-10-14

1-2 数组元素的区间删除

分数 5

作者 DS课程组

单位浙江大学

给定一个顺序存储的线性表，请设计一个函数删除所有值大于min而且小于max的元素。删除后表中剩余元素保持顺序存储，并且相对位置不能改变。

函数接口定义：

1	int Delete( int A[], int L, int minA, int maxA );

其中A是整型数组，存储原始线性表的元素；L是表长，即A中元素的个数；minA和maxA分别为待删除元素的值域的下、上界。函数Delete应将A中所有值大于minA而且小于maxA的元素删除，同时保证表中剩余元素保持顺序存储，并且相对位置不变，最后返回删除后的表长。

裁判测试程序样例：

#include <stdio.h>

#define MAXN 20

int Delete( int A[], int L, int minA, int maxA );

int main()
{
    int A[MAXN], L, minA, maxA, i;

    scanf("%d", &L);
    for (i=0; i<L; i++) scanf("%d", &A[i]);
    scanf("%d %d", &minA, &maxA);
    L = Delete(A, L, minA, maxA);
    for (i=0; i<L; i++) printf("%d ", A[i]);
    printf("\n");

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

1
2
3

10
4 -8 2 12 1 5 9 3 3 10
0 4

输出样例：

1	4 -8 12 5 9 10

答案

int Delete( int A[], int L, int minA, int maxA ) {
    int i = 0;
    while (i != L) {
        if (A[i] > minA && A[i] < maxA) {
            // 删除A[i]
            for (int j = i; j < L-1; j++) {
                A[j] = A[j+1];
            }
            L--;
        } else { // 往后看下一位是不是符合要删的条件
            i++;
        }
    }
    return L;
}

太妙了：

如果符合要删的，就删掉，下一位要看的往前了，i不变
如果不符合要删的，就i++，看下一位

妙在用 “原位覆盖 + 单次遍历” 的极简逻辑，完美平衡了 “正确性、效率、空间复杂度”，没有多余操作，精准解决了 “删除区间元素 + 保持顺序” 的核心需求。具体妙点可拆解为 3 个维度：

一、逻辑极简：用 “遍历 + 条件保留” 替代复杂删除，思路直观

普通初学者可能会先标记所有要删除的元素，再统一移动剩余元素，或用额外数组存储保留元素 —— 但这个答案直接在原数组上操作，核心逻辑只有 “一句话”：

“遍历数组，遇到要删除的元素就用后续元素覆盖它（相当于删除），遇到要保留的元素就往后走”。

代码里的 while (i != L) 循环是核心：

当 A[i] 是 “要删除的（minA <= A[i] <= maxA）”：用 j 循环把 i 后面的元素往前挪 1 位（覆盖 A[i]），同时表长 L--（因为删了一个元素），且 i 不递增（因为覆盖后 A[i] 变成了原 A[i+1]，需要重新判断这个新元素）。
当 A[i] 是 “要保留的”：i++ 继续判断下一个元素。