这道题给了个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"); } }
#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; }
这道题给了个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))$。
下面是参考代码：