集合的交和并算法

给出两个由数字组成的集合，请求这两个集合的“交”和“并”。

输入格式:

给一个n，m 代表两个数列的大小 (0 <= n,m <=2e5)

如果n>0，则接下来一行， n个数空格隔开，代表第一个集合中的数。

如果m>0，则接下来一行， m个数空格隔开，代表第二个集合中的数。

-1e9<=ai,bi<=1e9

输出格式:

第一行首先输出两个数列交的集合中元素个数，如果元素个数大于0，则紧接着在这行输出“交集”的元素，按数值大小升序排列（本行输出多个数据时，用空格隔开，如果只有一个元素个数，行末无空格）

第二行首先输出两个数列并的集合中元素个数，如果元素个数大于0，则紧接着在这行输出“并集”的元素，按数值大小升序排列（本行输出多个数据时，用空格隔开，如果只有一个元素个数，行末无空格）

输入样例1:

1 3
1
1 3 4

输出样例1:

1 1
3 1 3 4

输入样例2:

1 3
1
2 3 4

输出样例2:

0
4 1 2 3 4

题解

利用双指针，先对两个数组排序，求交集和并集都是从前向后遍历。交集输出相等的元素，并集求解时每次将两个数组中较小的元素放入并集答案，最后再把未遍历完整的数组加进去。

/*1.将数据读入vector v1 v2中
2.将v1,v2排序
3.双指针的方法记录交集值
4.用双指针,每一次将较小的放进并集
5.输出
*/
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n, m, a = 0, b = 0;
  cin >> n >> m;
  vector<int> v1(n), v2(m), J, B;//J是交集，B是并集
  for (int i = 0; i < n; i++) cin >> v1[i];
  for (int i = 0; i < m; i++) cin >> v2[i];
  sort(begin(v1), end(v1));
  sort(begin(v2), end(v2));
  while (a < n && b < m) {
    if (v1[a] < v2[b]) {
      B.push_back(v1[a]);
      a++;
    } else if (v1[a] > v2[b]) {
      B.push_back(v2[b]);
      b++;
    } else {
      J.push_back(v1[a]);
      b++;
    }
  }
  if (a==n) {
    for (int b_temp=b; b_temp < m; b_temp++) B.push_back(v2[b_temp]);
  } else {
    for (int a_temp=a; a_temp < n; a_temp++) B.push_back(v1[a_temp]);
  }
  if (J.size()) {
    cout << J.size();
    for (auto temp : J) {
      cout <<" "<< temp;
    }
    cout << endl;
  } else {
    cout << "0" << endl;
  }
  cout << B.size() ;
  for (auto temp : B) {
    cout <<" "<< temp ;
  }
  system("pause");
}

需要注意的是，PTA平台如果输出的空格不一致，就会造出格式错误，在循环时尤其要注意末尾是不是多加了空格，本题由于先输出了数组个数，循环时先输出空格即可，如果是一般题目，可以像下面这样。

如果输出内容有多行时候，通过循环结构实现输出很容易会多一个换行符。

  for(i=1;i<=5;i++)   printf("hello\n"); 

上面代码运行没任何问题，输出了5行hello，但是最后一个hello还会多了一个\n，就是会换行。 但是多的这个换行符就会和题目要求输出不匹配，一般PTA题目输出多行内容，最后一行都没有换行符，所以这段代码提交还是会犯格式错误问题。怎么解决呢？

• 1.最后一项单独判断

  for(i=1;i<=5;i++)
    {
       if(i==5) printf("hello");
       else printf("hello\n"); 
    }

• 2.最后一项不好确定，引入flag

int flag=1; 
for(i=1;i<=5;i++)
    {
       if(flag)  {printf("hello");flag=0;}
       else printf("\nhello"); 
    }

上述代码输出的5行hello，就可以去掉尾部换行符。还有尾部多空格符，一样处理。你也可以根据题目具体输出要求修改你的程序。

---