PTA（顺序表）2-5 集合减法

2-5 集合减法

分数 6

作者 朱允刚

单位 吉林大学

给定两个非空集合A和B，集合的元素为30000以内的正整数，编写程序求A-B。

输入格式:

输入为三行。第1行为两个整数n和m，分别为集合A和B包含的元素个数，1≤n, m ≤10000。第2行表示集合A，为n个空格间隔的正整数，每个正整数不超过30000。第3行表示集合B，为m个空格间隔的正整数，每个正整数不超过30000。

输出格式:

输出为一行整数，表示A-B，每个整数后一个空格，各元素按递增顺序输出。若A-B为空集，则输出0，0后无空格。

输入样例:

1
2
3
5 5
1 2 3 4 5
3 4 5 6 7

输出样例:

1
1 2

我的超时代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
using namespace std;

// 定义顺序表结构
typedef struct {
    int *data;
    int length;
} sqList;

// 初始化顺序表
void initList(sqList &L, int n) {
    L.data = new int[n];
    L.length = 0;
}

// 在顺序表里面找元素x
int findELem(sqList L, int x) {
    for (int i = 0; i < L.length; ++i) {
        if (L.data[i] == x) {
            return i; // 找到了返回下标i
        }
    }
    return -1; // 没找到，返回-1
}

int main() {
    int n, m;
    cin >> n >> m;
    sqList L1;
    sqList L2;
    initList(L1, n);
    initList(L2, m);
    // 将元素读取进顺序表L1
    for (int i = 0; i < n; ++i) {
        cin >> L1.data[i];
        L1.length++;
    }
    // 将元素读取进顺序表L2
    for (int i = 0; i < m; ++i) {
        cin >> L2.data[i];
        L2.length++;
    }
    // 遍历L2，将L2中L1有的，从L1中删除
    for (int i = 0; i < m; ++i) {
        int isFind = findELem(L1, L2.data[i]);
        if (isFind != -1) { // 如果找到了
            // 把要删的元素后面的往前挪
            for (int j = isFind; j < L1.length-1; j++) {
                L1.data[j] = L1.data[j+1];
            }
            // 表长减一个
            L1.length--;
        }
    }
    // 输出两个集合减之后的表
    if (L1.length != 0){
        for (int i = 0; i < L1.length; ++i) {
            cout << L1.data[i] << " ";
        }
    } else { // 题目要求空集就输出0
        cout << "0";
    }
}

1. 查找操作 (findELem)

  • 操作： 在顺序表 L1 (集合 A) 中查找元素 L2.data[i]。
  • 时间复杂度： findELem 函数使用线性遍历。在最坏情况下（元素在表尾或不存在），它需要检查 N 个元素。
  • 结论： 查找操作的时间复杂度为 O(N)，其中 N 是集合 A 的当前长度。

2. 删除操作（移动元素）

  • 操作： 当元素找到后，将其从顺序表 L1 中删除。由于顺序表是连续存储的，删除一个元素需要将该元素之后的所有元素向前移动一位。
  • 时间复杂度： 在最坏情况下（删除第一个元素），需要移动 N−1 个元素。
  • 结论： 删除操作的时间复杂度为 O(N)。

3. 总体时间复杂度

  • 外层循环遍历集合 B，执行 M 次。
  • 内层循环中，每次迭代都执行一次 O(N) 的查找和一次最坏 O(N) 的删除。

因此，整个集合减法操作的总时间复杂度为：

总时间≈M×(查找时间+删除时间)=M×(O(N)+O(N))=O(M×N)

4. 为什么会超时

根据题目约束，集合 A 的元素个数 N 和集合 B 的元素个数 M 都可达 10000。

最坏情况下，操作次数将达到：

10000×10000=108 次

解决

为了解决超时问题，我将查找操作从 O(N) 优化到了 O(1)（常数时间）。

  • 我引入了一个布尔数组 exists（大小为 30001）。
  • 这个数组相当于一个高效的查找表。
  • 通过检查 exists[x] 的值，我们可以在瞬间判断元素 x 是否在集合 B 中，这完全取代了 findELem 的作用。

正确代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>

using namespace std;

// 最大元素值
const int MAX_ELEM = 30000;
// 标记数组：exists[i] = true 表示 i 在集合 B 中
bool exists[MAX_ELEM + 1];

// 定义顺序表结构
typedef struct {
    int *data;
    int length;
} sqList;

// 初始化顺序表(保持不变)
void initList(sqList &L, int n) {
    L.data = new int[n];
    L.length = 0;
}

// 在顺序表末尾添加元素
void pushBack(sqList &L, int x) {
    L.data[L.length] = x;
    L.length++;
}

int main() {
    int n, m;
    cin >> n >> m;
    sqList A;

    initList(A, n);

    // 将元素读取进顺序表A
    for (int i = 0; i < n; ++i) {
        cin >> A.data[i];
        A.length++;
    }

    // 初始化标记数组
    for (int i = 1; i <= MAX_ELEM; ++i) {
        exists[i] = false;
    }

    // 将元素读取进集合B并标记（取代读取进顺序表B）
    for (int i = 0; i < m; ++i) {
        int b_val;
        cin >> b_val;
        // 在标记数组中记录B中的元素 (O(M))
        exists[b_val] = true;
    }

    // 创建结果顺序表，最大容量为n
    sqList resultList;
    initList(resultList, n);

    // 集合减法优化： 遍历B，将A中不在B（即未被标记）的元素移到结果集合中。
    // 这避免了O(N*M)的查找和删除操作。 (O(N))
    for (int i = 0; i < A.length; ++i) {
        int val = A.data[i];
        if (!exists[val]) {
            pushBack(resultList, val);
        }
    }

    // 输出两个集合减之后的表
    if (resultList.length == 0){
        // 题目要求空集就输出0，0后无空格
        cout << "0";
    } else {
        // 题目要求每个整数后一个空格（包括最后一个）
        for (int i = 0; i < resultList.length; ++i) {
            cout << resultList.data[i] << " ";
        }
    }
    cout << "\n";
}