27. 集合交并差

Deuchie

这道题给了个STL的标签,应该是想考察对Algorithm里的「求交集」「求并集」「求差集」三个函数的应用。

这三个函数的参数是:
1. A容器首迭代器
2. A容器尾迭代器
3. B容器首迭代器
4. B容器尾迭代器
5. 结果存储容器首迭代器

返回值是存储的内容的尾迭代器。所以可以用它来减去首迭代器得到元素个数。注意如果输入容器中有相同元素可能会影响结果。

C++语言这三个函数的局限是要求必须有序。这比Java, Python的要求更严格一些。

你可以通过使用一个unordered_set(即hash_set)来在 $O(A+B)$ 时间内完成并集操作,而不是先排序的 $O((A+B)\log(A+B))$。

下面是参考代码:

#include <algorithm>
#include <cstdio>
#include <memory>
using namespace std;

int main() {
    int a, b;
    scanf("%i%i", &a, &b);
    auto pa = make_unique<int[]>(a);
    auto pb = make_unique<int[]>(b);
    auto pc = make_unique<int[]>(a + b);
    for (int i = 0; i < a; ++i)
        scanf("%i", &pa[i]);
    for (int i = 0; i < b; ++i)
        scanf("%i", &pb[i]);
    sort(pa.get(), pa.get() + a);
    sort(pb.get(), pb.get() + b);
    int sz = set_intersection(pa.get(), pa.get() + a, pb.get(), pb.get() + b, pc.get()) - pc.get();
    if (sz == 0)
        printf("{}\n");
    else {
        printf("{%i", pc[0]);
        for (int i = 1; i < sz; ++i)
            printf(",%i", pc[i]);
        printf("}\n");
    }
    sz = set_union(pa.get(), pa.get() + a, pb.get(), pb.get() + b, pc.get()) - pc.get();
    if (sz == 0)
        printf("{}\n");
    else {
        printf("{%i", pc[0]);
        for (int i = 1; i < sz; ++i)
            printf(",%i", pc[i]);
        printf("}\n");
    }
    sz = set_difference(pa.get(), pa.get() + a, pb.get(), pb.get() + b, pc.get()) - pc.get();
    if (sz == 0)
        printf("{}\n");
    else {
        printf("{%i", pc[0]);
        for (int i = 1; i < sz; ++i)
            printf(",%i", pc[i]);
        printf("}\n");
    }
}
Kinoko
#include <cstdio>
#include <algorithm>
#include <set>
#include <iterator>
using namespace std;

int main()
{
    int n, m, num;
    set<int> a, b, i_set, u_set, d_set;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        a.insert(num);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d", &num);
        b.insert(num);
    }
    set_intersection(a.begin(), a.end(), b.begin(), b.end(), inserter(i_set, i_set.begin()));
    set_union(a.begin(), a.end(), b.begin(), b.end(), inserter(u_set, u_set.begin()));
    set_difference(a.begin(), a.end(), b.begin(), b.end(), inserter(d_set, d_set.begin()));

    printf("{");
    for (auto it = i_set.begin(); it != i_set.end(); it++)
        printf("%s%d", it != i_set.begin() ? "," : "", *it);
    printf("}\n");
    printf("{");
    for (auto it = u_set.begin(); it != u_set.end(); it++)
        printf("%s%d", it != u_set.begin() ? "," : "", *it);
    printf("}\n");
    printf("{");
    for (auto it = d_set.begin(); it != d_set.end(); it++)
        printf("%s%d", it != d_set.begin() ? "," : "", *it);
    printf("}\n");
    return 0;
}
你当前正在回复 博客/题目
存在问题!