Intersecția a doi vectori sortați în C++

Intersecția conține valorile prezente în ambii vectori. Pentru 1 2 2 5 și 2 2 3 5, rezultatul cerut aici este 2 5: fiecare valoare apare o singură dată. Dacă o problemă cere păstrarea multiplicităților, adică a numărului de copii, contractul și algoritmul trebuie adaptate.

Două poziții care avansează

Citim 0≤n,m≤1000, apoi cei doi vectori sortați nedescrescător. Afișăm numărul valorilor comune distincte, urmat de acestea pe a doua linie. O intersecție goală produce 0 și o linie goală. Tablourile clasice au fiecare capacitate 1000, indicii încep de la zero.

Poziția i indică prima valoare încă neprocesată din a, iar j pe cea din b. Dacă a[i]<b[j], valoarea a[i] nu se poate găsi de la j încolo în b, deoarece acolo toate valorile sunt cel puțin b[j]. Putem avansa i. Argumentul este simetric când a[i]>b[j].

La egalitate, am găsit o valoare comună. O scriem o singură dată în rezultat, apoi sărim peste toate copiile ei în ambii vectori. Continuăm până când unul se termină; din acel moment nu mai există o pereche de valori neprocesate de comparat.

Vectorii 1,2,2,5 și 2,2,3,5 au valorile comune distincte 2 și 5. Repetările nu multiplică rezultatul.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    int a[1000],b[1000],c[1000];
    for(int i=0;i<n;++i) cin >> a[i];
    for(int j=0;j<m;++j) cin >> b[j];
    int i=0,j=0,k=0;
    while(i<n && j<m) {
        if(a[i]<b[j]) ++i;
        else if(a[i]>b[j]) ++j;
        else {
            int x=a[i]; c[k++]=x;
            while(i<n && a[i]==x) ++i;
            while(j<m && b[j]==x) ++j;
        }
    }
    cout << k << '\n';
    for(int t=0;t<k;++t) cout << (t?" ":"") << c[t];
    cout << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
using namespace std;
int main() {
    int n,m; cin >> n >> m;
    vector<int> a(n),b(m),c(n);
    for(int i=0;i<n;++i) cin >> a[i];
    for(int j=0;j<m;++j) cin >> b[j];
    int i=0,j=0,k=0;
    while(i<n && j<m) {
        if(a[i]<b[j]) ++i;
        else if(a[i]>b[j]) ++j;
        else {
            int x=a[i]; c[k++]=x;
            while(i<n && a[i]==x) ++i;
            while(j<m && b[j]==x) ++j;
        }
    }
    cout << k << '\n';
    for(int t=0;t<k;++t) cout << (t?" ":"") << c[t];
    cout << '\n';
}

Urmărește duplicatele explicit

Pe exemplul inițial, 1 este eliminat din a deoarece este mai mic decât 2 din b. Egalitatea 2=2 produce un singur 2; indicii sar apoi peste ambele copii din fiecare vector. Valoarea 3 din b este mai mică decât 5 din a și este eliminată. Ultima egalitate produce 5.

Rezultatul are cel mult min(n,m) elemente. În versiunea vector am rezervat n poziții pentru c, un plafon suficient; k descrie câte sunt efectiv folosite. Verificările i<n și j<m trebuie să apară înaintea accesului la a[i] și b[j]. Operatorul && oprește evaluarea când prima condiție este falsă.

Fiecare indice avansează cel mult până la capăt, fără reveniri, deci timpul este O(n+m). Rezultatul ocupă O(min(n,m)) elemente utile, iar tabloul rezervat poate fi mai mare. Nu afirmăm memorie totală constantă deoarece stocăm vectorii.

Exersează

Verifică doi vectori fără valori comune, doi identici și un vector gol. Pentru 2 2 2 și 2, ieșirea conține un singur 2. Explică ce ar trebui schimbat dacă s-ar cere atâtea copii cât minimul frecvențelor din cele două intrări.

Continuă cu interclasarea, frecvențele și căutarea.

Întrebări frecvente

Cum găsesc intersecția a doi vectori sortați?

Folosește câte un indice în fiecare vector. Avansează în vectorul cu valoarea curentă mai mică; la egalitate ai găsit o valoare comună. Fiecare indice avansează fără să revină.

Se păstrează duplicatele în intersecția din această lecție?

Nu. Fiecare valoare comună este afișată o singură dată. Pentru 1 2 2 5 și 2 2 3 5, rezultatul este 2 5.

Ce complexitate are intersecția prin doi indici?

O(n+m) timp pentru vectori de lungimi n și m, deoarece fiecare element este depășit cel mult o dată. Spațiul rezultatului depinde de numărul valorilor comune păstrate.