ALGO-10-view

柔光的暖阳◎ 2022-12-11 13:58 94阅读 0赞

O(Na\*Nb)全部换成O(max(Na, Nb))了  
我不清楚测试数据 是否都是递增的集合，我直接默认了

#include <iostream>
    #include <cstdlib>
    
    using namespace std;
    const int maxn = 1e3 + 5;
    int Na, Nb, flag;
    int i, j;
    int vis[maxn], A[maxn], B[maxn];
    
    int main()
    {
        
        cin >> Na;
        for (i = 0; i < Na; i++)
            cin >> A[i];
        cin >> Nb;
        for (i = 0; i < Nb; i++)
            cin >> B[i];
        //求交集
        flag = 0;
        for (i = 0, j = 0; i < Na && j < Nb;)
        {
        
            if(A[i] > B[j]) j++;
            else if (A[i] < B[j]) i++;
            else {
        
                if (flag++) cout << " ";
                cout << A[i];
                i++;
                j++;
            }
        }
        cout << endl;
        //求并集
        flag = 0;
        for (i = 0, j = 0; i < Na && j < Nb;)
        {
        
            if (flag++) cout << " ";
            if(A[i] > B[j]) 
            {
        
                cout << B[j++];
            }
            else if (A[i] < B[j]) 
            {
        
                cout << A[i++];
            }
            else {
        
                cout << A[i];
                i++;
                j++;
            }
        }
        if (i <= Na)
        {
        
            for (; i <= Na; i++)
            {
        
                if (flag++) cout << " ";
                cout << A[i];
            }
        }
        if (j <= Nb)
        {
        
            for (;j <= Nb; j++)
            {
        
                if (flag++) cout << " ";
                cout << B[j];
            }
        }
        cout << endl;
        //求对称差？不知道该怎么定义这种输出
        flag = 0;
        for (i = 0, j = 0; i < Na && j < Nb;)
        {
        
            if(A[i] > B[j]) j++;
            else if (A[i] < B[j]) i++;
            else {
        
                A[i] = 0;
                i++;
                j++;
            }
        }
        for (int i = 0; i < Na; i++)
        {
        
            if (A[i] != 0)
            {
        
                if (flag++) cout << " ";
                cout << A[i];
            }
        }
        cout << endl;
        system("pause");
        return 0;
    }