Operatii pe multimi de numere naturale

Operatii pe multimi de numere naturale este un subiect interesant care merita discutat.

Se dau 2 multimi de numere naturale A si B cu maxim 200000 de elemente mai mici de 1000000000. Determinati diferenta A-B, reuniunea, intersectia si diferenta simetrica a celor doua multimi.

Problema poate fi gasita si pe site pbinfo cu numarul #3974.

Algoritmul trebuie rezolvat folosind bibliotecile standard STL pentru a respecta cerintele pbinfo si pentru a prim 100 de puncte.

Pentru a fi intelese operatiile care trebuie implementate in ideea redactarii algoritmului fara STL, vom prezenta mai multe idei de rezolvare, astfel incat cel care doreste sa inteleaga sa poata alege mai multe abordari de rezolvare.

Operatiile pe multimile care se cer implementare sunt:

– reuniunea – elementele comune si necomune din cele doua multimi, luate o singura data;

– intersectia – elementele comune din cele doua multimi, luate o singura data;

– diferenta – elementele care apartin primei multimi si nu apartin celei de a doua multimi;

– diferenta simetrica – reuniunea dintre diferentele (A-B) si (B-A)

Un prim algoritm in care am detaliat fiecare operatie in parte ar fi:

#include <iostream>

using namespace std;

int n,m,x,a[200010],b[200010],r[400010],difAB[200010],difBA[200010],aux,i,j,k;
char c;
int getNumber(){
    int number;
    cin >> number;
    return number;
}
char getChar(){
    char caracter;
    cin >> caracter;
    return caracter;
}
void citesteVector(int v[], int lv) {
    int i;
    for (i = 1; i <= lv; i++)
    {
        cin >> v[i];
    }
}
void sortCrescator(int v[], int lv){
    for (i=1; i<=lv; i++)
        for (j=i+1; j<=lv; j++)
            if (v[i]>v[j]) {
                    aux = v[i]; v[i] = v[j]; v[j]=aux;
            }
}

void interclasare(int v[], int lv, int u[], int lu){
    v[lv+1]=u[lu]+1;
    u[lu+1]=v[lv]+1;
    for (i=j=k=1; k<=lv+lu; k++) {
        if (v[i]<u[j]){
            r[k] = v[i];
            i++;
        }else{
            r[k] = u[j];
            j++;
        }
    }
}
void reuniuneMultimi(int v[], int lv){
    for (i=1; i<=lv; i++) {
      if (v[i]!=v[i+1]) {
            cout<<v[i]<<" ";
      }
    }
}

void intersectieMultimi(int v[], int lv){
    for (i=1; i<=lv; i++) {
      if (v[i]==v[i+1]) {
            cout<<v[i]<<" ";
      }
    }
}

void diferentaMultimi(int v[], int lv, int u[], int lu){
    for (i=1; i<=lv; i++) {
        int gasit=1;
        for (j=1; j<=lu; j++) {
            if (v[i]==u[j]){gasit=0;}
        }
        if (gasit==1){cout<<v[i]<<" ";}
    }
}

void tiparesteVector(int v[], int lv) {
    int i;
    for (i = 1; i <= lv; i++)
    {
        cout << v[i]<<" ";
    }
}

void diferentaSimetricaMultimi(int v[], int lv, int u[], int lu){
    //(a-b)+(b-a)
    int difab=1;
    for (i=1; i<=lv; i++) {
        int gasit=1;
        for (j=1; j<=lu; j++) {
            if (v[i]==u[j]){gasit=0;}
        }
        if (gasit==1){
            difAB[difab]=v[i];
            difab++;
        }
    }
    difab--;
    tiparesteVector(difAB,difab);
    cout<<endl;

    int difba=1;
    for (i=1; i<=lu; i++) {
        int gasit=1;
        for (j=1; j<=lv; j++) {
            if (u[i]==v[j]){gasit=0;}
        }
        if (gasit==1){
            difBA[difba]=u[i];
            difba++;
        }
    }
    difba--;
    tiparesteVector(difBA,difba);
    cout<<endl;
    interclasare(difAB,difab,difBA,difba);
    reuniuneMultimi(r,difab+difba);
}

int main() {
    m=getNumber();
    n=getNumber();
    c=getChar();
    citesteVector(a,m);
    sortCrescator(a,m);
    citesteVector(b,n);
    sortCrescator(b,n);
    interclasare(a,m,b,n);
    switch(c)
    {
        case '*':   {
                        intersectieMultimi(r,m+n);
                        break;
                    }
        case '+':   {
                        reuniuneMultimi(r,m+n);
                        break;
                    }
        case '-':   {
                        //A-B
                        diferentaMultimi(a,m,b,n);
                        break;
                    }
        case '%':   {
                        //(A-B)+(B-A)
                        diferentaSimetricaMultimi(a,m,b,n);
                        break;
                    }
    }
    return 0;

}

Un alt algoritm functional ar putea fi acesta:

#include <iostream>

#define size 200010
using namespace std;

void citeste(int v[size], int lv) {
    for (int i=0; i<lv; i++) {
        cin>>v[i];
    }
}

void scrie(int v[size], int lv) {
    for (int i=0; i<lv; i++) {
        cout<<v[i]<<" ";
    }
}

void sorteaza(int v[size], int lv) {
    for (int i=0; i<lv; i++) {
        for (int j=i+1; j<lv; j++) {
            if (v[i]>v[j]) {
                swap(v[i], v[j]);
            }
        }
    }
}

bool cauta(int v[size], int lv, int el) {
    for (int i=0; i<lv; i++) {
        if (v[i] == el) {
            return true;
        }
    }

    return false;
}

void intersectia(int a[size], int la, int b[size], int lb, int r[size], int &lr) {
    for (int i=0; i<la; i++) {
        if (cauta(b, lb, a[i])) {
            r[lr++] = a[i];
        }
    }
    sorteaza(r,lr);
}

void reuniunea(int a[size], int la, int b[size], int lb, int r[size], int &lr) {
    for (int i=0; i<lb; i++) {
        r[lr++] = b[i];
    }
    for (int i=0; i<la; i++) {
        if (!cauta(b, lb, a[i])) {
            r[lr++] = a[i];
        }
    }
    sorteaza(r,lr);
}

void diferenta(int a[size], int la, int b[size], int lb, int r[size], int &lr) {
    for (int i=0; i<la; i++) {
        if (!cauta(b, lb, a[i])) {
            r[lr++] = a[i];
        }
    }
    sorteaza(r,lr);
}

void diferentaSimetrica(int a[size], int la, int b[size], int lb, int r[size], int &lr) {
    int r1[size],lr1=0;
    int r2[size],lr2=0;
    diferenta(a,la,b,lb,r1,lr1);
    diferenta(b,lb,a,la,r2,lr2);
    reuniunea(r1,lr1,r2,lr2,r,lr);
    sorteaza(r,lr);
}

int main(){
    int la=0, lb=0, lr=0;
    int a[size], b[size], r[size];
    char op;

    cin>>la>>lb>>op;
    citeste(a,la); citeste(b,lb);
    switch (op){
        case '*': intersectia(a,la,b,lb,r,lr);break;
        case '+': reuniunea(a,la,b,lb,r,lr);break;
        case '-': diferenta(a,la,b,lb,r,lr);break;
        case '%': diferentaSimetrica(a,la,b,lb,r,lr);break;
    }
    
    scrie(r,lr);
    return 0;
}

Nici unul dintre acesti algoritmi nu se incadreaza in limitele de timp cerute de problema, dar sunt utile pentru a intelege algoritmii implementati pentru fiecare operatie in parte.

Solutia care primeste 100 de puncte este realizata cu STL.

#include <bits/stdc++.h>

using namespace std;

char op;

int N, M;

int main() {

    cin >> N >> M >> op;

    vector <int> a(N);
    for(int i = 0;i < N;i++)
        cin >> a[i];

    vector <int> b(M);
    for(int i = 0;i < M;i++)
        cin >> b[i];

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    vector <int> res(N + M);
    if(op == '*') res.resize(set_intersection(a.begin(), a.end(), b.begin(), b.end(), res.begin()) - res.begin());
    if(op == '+') res.resize(set_union(a.begin(), a.end(), b.begin(), b.end(), res.begin()) - res.begin());
    if(op == '-') res.resize(set_difference(a.begin(), a.end(), b.begin(), b.end(), res.begin()) - res.begin());
    if(op == '%') res.resize(set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), res.begin()) - res.begin());

    for(int x : res)
        cout << x << " ";

    return 0;
}