Forming New Sets
Just as numbers can be added, subtracted, and multiplied, we can manipulate sets in certain basic ways. The natural operations on sets are to combine their elements, to find those elements common to both sets, and to determine which elements belong to one set but not another.
Just as graph theory is the mathematical study of graphs and their properties, set theory is the mathematical study of sets and their properties.
Problem
If A and B are sets, then their union A∪B is the set comprising any elements in either A or B; their intersection A∩B is the set of elements in both A and B; and their set difference A−B is the set of elements in A but not in B.
Furthermore, if A is a subset of another set U, then the set complement of A with respect to U is defined as the set Ac=U−A. See the Sample sections below for examples.
Given: A positive integer n (n≤20,000) and two subsets A and B of {1,2,…,n}.
Return: Six sets: A∪B, A∩B, A−B, B−A, Ac, and Bc (where set complements are taken with respect to {1,2,…,n}
Sample Dataset
10
{1, 2, 3, 4, 5}
{2, 8, 5, 10}
Sample Output
{1, 2, 3, 4, 5, 8, 10}
{2, 5}
{1, 3, 4}
{8, 10}
{8, 9, 10, 6, 7}
{1, 3, 4, 6, 7, 9}
Extra Information
From the definitions above, one can see that A∪B=B∪A and A∩B=B∩A for all sets A and B, but it is not necessarily the case that A−B=B−A (as seen in the Sample sections above). This set theoretical fact parallels the arithmetical fact that addition is commutative but subtraction is not.
Solution
本例不打算使用内置数据结构，因为这样解题没有意思。同时也不打算实现性能好的平衡树，只使用排序数组进行模拟。
算法流程：
- 定义 有序 全集
，对输入两个集合放入数组后排序。 - 执行相关集合操作。
由于两个集合都是有序的，因此可以加快查找，所以在下面操作中将会使用 双指针 策略，用 
索引指向 
中元素即 
；用 
索引指向 
中元素即 
。
（1）并集：
- 当
，此时只需要添加任一一个数字即可。同时 ++i, ++j - 若
：- 因为
，即之后不可能重复出现 ，添加 ，同时 ++i - 为避免重复
j指针不动 ，因为
可能有元素与 相等
- 因为
- 若
：- 因为
，即之后不可能重复出现 ，添加 ，同时 ++j - 为避免重复
i指针不动，因为
可能有元素与 相等
```
i = 0, j = 0: A[i] < B[j] 添加 A[i], 则 A∪B = {1}; ++i
A: 1 2 8
i
B: 2 5 8 10
j
- 因为
i = 1, j = 0: A[i] = B[j] 添加 A[i]/B[j], 则 A∪B = {1, 2}; ++i, ++j A: 1 2 8 i B: 2 5 8 10 j
i = 2, j = 1: A[i] > B[j] 添加 B[j], 则 A∪B = {1, 2, 5}; ++j A: 1 2 8 i B: 2 5 8 10 j
i = 2, j = 2: A[i] = B[j] 添加 A[i]/B[j], 则 A∪B = {1, 2, 5, 8}; ++i,++j A: 1 2 8 i B: 2 5 8 10 j
i = 3, j = 3: i 超界，添加剩余 B[j+1,n) ，则 A∪B = {1, 2, 5, 8, 10} A: 1 2 8 i B: 2 5 8 10 j
<a name="DyXN0"></a>### （2）交集：1. 当 ，此时只需要添加任一**一个数字**即可。同时 `++i, ++j`1. 若 ：- 因为 ，即之后不可能重复出现 ，因此 `++i`- 为避免遗漏 `j` 指针不动 ，因为  可能有元素与  相等- 若 ：- 因为 ，即之后不可能重复出现 ，因此 `++j`- 为避免遗漏 `i` 指针不动，因为  可能有元素与  相等
i = 0, j = 0: A[i] < B[j], 则 ++i; A: 1 2 3 4 5 i B: 2 5 8 10 j
i = 1, j = 0: A[i] = B[j] 添加 A[i]/B[j], A∩B = {2}; ++i, ++j A: 1 2 3 4 5 i B: 2 5 8 10 j
i = 2, j = 1: A[i] < B[j], 则 ++i; A: 1 2 3 4 5 i B: 2 5 8 10 j
i = 3, j = 1: A[i] < B[j], 则 ++i; A: 1 2 3 4 5 i B: 2 5 8 10 j
i = 4, j = 1: A[i] = B[j] 添加 A[i]/B[j], A∩B = {2, 5}; ++i, ++j A: 1 2 3 4 5 i B: 2 5 8 10 j
i = 5, j = 2: i 超界，不可能再有交集 A: 1 2 3 4 5 i B: 2 5 8 10 j
<a name="UaTeU"></a>### （3）补集：假设两个集合都是有序的且有 ，因此我们可以使用双指针直接 `pick` 非  元素即可，遍历  元素：1. 若  则不将当前  记录，1. 若 ：- 因为 ，即之后不可能重复出现 ，因此添加  元素，同时 `++i`- 为避免重复 `j` 指针不动 ，因为  可能有元素与  相等3. 若 ：- 因为 ，即之后不可能重复出现 ，同时 `++j`- 为避免重复 `i` 指针不动 ，因为  可能有元素与  相等
i = 0, j = 0: C[i] = A[j], 则 ++i, ++j; C: 1 2 4 5 6 7 8 i A: 1 3 4 j
i = 0, j = 0: C[i] < A[j], 添加 C[i], A ^ C = {2} ;++i, ++j;
C: 1 2 4 5 6 7 8
i
A: 1 3
j
i = 2, j = 1: C[i] > A[j]，可能 A[j+1,n) 存在 C[i]; ++j; C: 1 2 4 5 6 7 8 i A: 1 3 4 j
<a name="JtzFU"></a>### （4）差集：根据上面所求交集，我们就可以得到 ，也就是它们各自去除交集的补集。直接调用上面补集函数即可。```cpp#include <iostream>#include <vector>#include <algorithm>using namespace std;class Set {public:Set() {};Set(vector<int> &nums) {// 假设输入 nums 不包含重复值for (auto num: nums) add(num);sort(sortNums.begin(), sortNums.end()); // 排序};void add(int val) {sortNums.push_back(val);}void printSet() {cout << "{";int n = sortNums.size();for (int i = 0; i < n - 1; ++i) cout << sortNums[i] << ", ";if (n > 0) cout << sortNums[n-1];cout << "}" << endl;}Set unite(Set &t) {int m = this->sortNums.size(), i = 0;int n = t.sortNums.size(), j = 0;Set res;while (i < m && j < n) {if (this->sortNums[i] == t.sortNums[j]) {res.add(this->sortNums[i]);++i, ++j;} else if (this->sortNums[i] < t.sortNums[j]) {res.add(this->sortNums[i]);++i;} else {res.add(t.sortNums[j]);++j;}}while (i < m) res.add(this->sortNums[i++]);while (j < n) res.add(t.sortNums[j++]);return res;}Set intersection(Set &t) {int m = this->sortNums.size(), i = 0;int n = t.sortNums.size(), j = 0;Set res;while (i < m && j < n) {if (this->sortNums[i] == t.sortNums[j]) {res.add(this->sortNums[i]);++i, ++j;} else if (this->sortNums[i] < t.sortNums[j]) {++i;} else {++j;}}return res;}Set difference(Set &t) {// s - tint m = this->sortNums.size(), i = 0;int n = t.sortNums.size(), j = 0;Set res;while (i < m && j < n) {if (this->sortNums[i] == t.sortNums[j]) {++i, ++j;} else if (this->sortNums[i] < t.sortNums[j]) {res.add(this->sortNums[i]);++i;} else {++j;}}while (i < m) res.add(this->sortNums[i++]); // t 中没有全部加入return res;}Set compliment(Set &c) {// c 是全集return c.difference(*this);}private:vector<int> sortNums;};vector<int> extractNumber(string &s) {int i = 0, n = s.size();vector<int> ret;while (i < n) {while (i < n && !isdigit(s[i])) ++i; // 跳过非数字字符if (i >= n) break;int num = 0;while (i < n && isdigit(s[i])) num = num * 10 + (s[i++] - '0');ret.push_back(num);}return ret;}int main() {int n;cin >> n;getchar(); // \nstring tmp;// getline 读入一行getline(cin, tmp, '\n');vector<int> ret = extractNumber(tmp);Set A(ret);getline(cin, tmp, '\n');ret = extractNumber(tmp);Set B(ret);vector<int> c(n);for (int i = 0; i < n; ++i) c[i] = i + 1;Set C(c);// A∪BA.unite(B).printSet();// A∩BA.intersection(B).printSet();// A-B, B-AA.difference(B).printSet();B.difference(A).printSet();// A^{C}, B^{C}A.compliment(C).printSet();B.compliment(C).printSet();return 0;}
若有收获，就点个赞吧
0 人点赞
