算法训练 集合运算

问题描述

　　给出两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。

输入格式

　　第一行为一个整数n，表示集合A中的元素个数。
　　第二行有n个互不相同的用空格隔开的整数，表示集合A中的元素。
　　第三行为一个整数m，表示集合B中的元素个数。
　　第四行有m个互不相同的用空格隔开的整数，表示集合B中的元素。
　　集合中的所有元素均为int范围内的整数，n、m<=1000。

输出格式

　　第一行按从小到大的顺序输出A、B交集中的所有元素。
　　第二行按从小到大的顺序输出A、B并集中的所有元素。
　　第三行按从小到大的顺序输出B在A中的余集中的所有元素。

样例输入

5
1 2 3 4 5
5
2 4 6 8 10

样例输出

2 4
1 2 3 4 5 6 8 10
1 3 5

样例输入

4
1 2 3 4
3
5 6 7

样例输出

1 2 3 4 5 6 7
1 2 3 4

思路：首先三种情况我都是先导入数组，然后排序后输出，交集和余集都好说，两层循环遍历即可，并集想了很久，我先把两个数组都导入一个新的数组，然后排序，然后再输入，重复的不予输出，即 arr3[i] != arr3[i - 1] ，才会输出。

学习：用sort对vector数组排序时，实参是 v.begin(),v.end() ,相应代码即 sort(arr3.begin(), arr3.end(), cmp) ， cmp 中若 return a < b; 是升序排列，反之是降序排列。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool cmp(int a, int b)
{
    return a < b;
}

int main()
{
    int arr1Num,arr2Num;
    int flag = 0;
    
    cin >> arr1Num;
    vector<int> arr1(arr1Num);
     for (int i = 0; i < arr1Num; i++)
    {
        cin >> arr1[i];
    }

    cin >> arr2Num;
    vector<int> arr2(arr2Num);
    for (int i = 0; i < arr2Num; i++)
    {
        cin >> arr2[i];
    }

    //交集
    int b[2000] = { 0 };
    int l = -1;
    for (int i = 0; i < arr1Num; i++)
    {
        for (int j = 0; j < arr2Num; j++)
        {
            if (arr1[i] == arr2[j])
            {
                flag = 1;  //有交集
                b[++l] = arr1[i];
            }
        }
    }
    if (flag == 1)  //有交集才输出换行
    {
        sort(b, b + l + 1, cmp);
        for (int i = 0; i < l + 1; i++)
        {
            cout << b[i] << " ";
        }
        cout << endl;
    }
    
    //并集
    vector<int> arr3(arr1Num+arr2Num);
    for (int i = 0; i < arr1Num; i++) //把两个数组的数字全导入arr3中
    {
        arr3[i] = arr1[i];
    }
    for (int j = arr1Num; j < arr1Num + arr2Num; j++)
    {
        arr3[j] = arr2[j - arr1Num];
    }
    sort(arr3.begin(), arr3.end(), cmp); //从小到大排序
    cout << arr3[0] << " ";
    for (int i = 1; i < arr1Num + arr2Num; i++)
    {
        if (arr3[i] != arr3[i - 1])
        {
            cout << arr3[i] << " ";
        }
    }
    cout << endl;

    //余集
    int i, j,k = -1;
    int a[2000] = { 0 };  //先记录下来
    int cnt = 0;
    for (i = 0; i < arr1Num; i++)
    {
        for (j = 0; j < arr2Num; j++)
        {
            if (arr1[i] == arr2[j])
            {
                break;
            }
        }
        if (j == arr2Num)
        {
            a[++k] = arr1[i];
            cnt++;
        }
    }
    sort(a, a + k + 1, cmp); //从小到大输出
    for (i = 0; i < cnt; i++)
    {
        cout << a[i] << " ";
    }
    return 0;
}