Vectori caracteristici

De ce contează?

La intrarea în cinema, supraveghetorul nu numără de câte ori ai mai venit — verifică doar dacă ai bilet: da sau nu. Un vector caracteristic face exact asta: pentru fiecare valoare posibilă, reține dacă există în colecție, nu de câte ori.

Ce este vectorul caracteristic?

Un vector caracteristic e o variantă binară a vectorului de frecvență:

caract[x] = 1 dacă valoarea x apare în colecție
caract[x] = 0 dacă x nu apare

Pentru mulțimea A = , vectorul caracteristic arată așa:

caract	0	1	0	1	0	1	0	1
valoare	0	1	2	3	4	5	6	7

caract[x] = 1 dacă x aparține mulțimii, 0 altfel.

Când vectorul caracteristic, când de frecvență?

Nevoie	Instrument
„Apare x?"	Caracteristic — `caract[x] == 1`
„De câte ori apare x?"	Frecvență — `frec[x]`
Operații cu mulțimi	Caracteristic
Elementul cu cele mai multe apariții	Frecvență

Algoritmul

#include <iostream>
using namespace std;

int caract[1001];   // global = 0

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        caract[x] = 1;   // marcare prezenta (nu ++)
    }

    int x;
    cin >> x;
    cout << (caract[x] ? "DA" : "NU") << "\n";
    return 0;
}

Operații cu mulțimi

// reuniune A ∪ B
for (int x = 0; x <= MAX; x++)
    cAUB[x] = cA[x] | cB[x];   // 1 daca in A sau in B

// intersectie A ∩ B
for (int x = 0; x <= MAX; x++)
    cAintB[x] = cA[x] & cB[x]; // 1 daca in ambele

// diferenta A \ B
for (int x = 0; x <= MAX; x++)
    cAdifB[x] = cA[x] & (!cB[x]); // 1 daca in A dar nu in B

Complexitate

Operație	Timp	Spațiu
Construire	O(n)	O(maxVal)
Interogare „x în mulțime?"	O(1)	—
Reuniune / intersecție	O(maxVal)	O(maxVal)

Observația-cheie

Reuniunea cu vectori caracteristici e O(maxVal), față de O(n·m) pentru varianta cu două parcurgeri imbricate. Când valorile sunt mici (sub 10.000), vectorii caracteristici sunt mult mai eficienți.

Vizualizare

Indiciu

La construcția caracteristicului, celula corespunzătoare valorii citite se colorează la 1. Vizualizatorul arată același mecanism ca frecvența — diferența e că scriem = 1, nu ++.

Greșeli frecvente

Greșeala 1: caract[x]++ în loc de caract[x] = 1 — funcționează pentru verificare, dar dacă mai târziu resetezi sau compari cu 1 strict, valorile > 1 creează confuzie. Semantica caracteristicului e 0/1.

Greșeala 2: Vrei să știi „de câte ori apare x" după ce ai construit doar caracteristicul — imposibil. Dacă ai nevoie de număr, folosești vectorul de frecvență.

Greșeala 3: Dimensiunea lui caract[] mai mică decât valoarea maximă posibilă — accesezi memorie invalidă.

Recapitulare

Vectorul caracteristic: caract[x] = 1 dacă x e prezent, 0 altfel.
Diferit de frecvență: marchează prezența, nu numără aparițiile.
Permite operații rapide cu mulțimi (reuniune, intersecție, diferență) în O(maxVal).