Vectori caracteristici

De ce contează?

La intrarea într-un club, un bodyguard bifează pe o listă cine a intrat deja. Nu-l interesează de câte ori a venit cineva — doar dacă e înăuntru sau nu: bifat / nebifat. Acesta e un vector caracteristic: pentru fiecare valoare, doar „prezent" sau „absent".

Ce este un vector caracteristic

Un vector caracteristic reține, pentru fiecare valoare posibilă, doar dacă e prezentă (1) sau nu (0). E ca un vector de frecvență, dar „turtit": nu te interesează de câte ori, ci doar dacă apare.

car	0	1	1	0	1	0	0	1
val	0	1	2	3	4	5	6	7

Vectorul caracteristic al mulțimii {1, 2, 4, 7}: 1 pe pozițiile prezente, 0 în rest. Indiferent de câte ori apare o valoare, marcajul rămâne 1.

Algoritm pas cu pas

Pentru datele {2, 5, 2, 7}, marcăm prezența:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool car[1001] = {false};       // initializat cu false (absent)
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        car[x] = true;              // marcam x ca prezent
    }

    // testam apartenenta in O(1)
    int q;
    cin >> q;
    cout << (car[q] ? "prezent" : "absent") << "\n";
    return 0;
}

Pentru {2, 5, 2, 7}, car[2] = car[5] = car[7] = true. Întrebarea „e 5 prezent?" → instant.

Observația-cheie

Marele câștig e testul de apartenență în O(1): car[x] îți spune imediat dacă x a apărut, fără să reparcurgi datele. E ideal pentru „am mai văzut valoarea asta?".

Aplicații tipice

Eliminarea duplicatelor: afișezi x doar dacă car[x] era încă false, apoi îl marchezi.
Apartenența la o mulțime: verifici instant dacă o valoare e în mulțime.
Bază pentru operații cu mulțimi: reuniune, intersecție, diferență (lecția următoare).

Complexitate

Operație	Timp	Spațiu
construire	O(n)	O(V)
test apartenență	O(1)	—

Greșeli frecvente

Capcane reale la vectorii caracteristici:

Folosești frecvența unde ajunge caracteristicul: dacă te interesează doar prezența, un bool e suficient și mai clar decât un contor.
Neinițializat: fără = {false}, pornești de la gunoi → apartenențe false.
Valoare peste dimensiune sau negativă: la fel ca la frecvență, dimensionează după valoarea maximă și folosește offset pentru negative.
Confuzi indexul cu valoarea: marchezi car[i] (poziția) în loc de car[x] (valoarea). Marcajul se face pe valoare.

Vizualizare

Vizualizarea de frecvență arată și prezența: o coloană nenulă înseamnă „valoarea există".

Indiciu

Pentru un vector caracteristic, te interesează doar dacă o coloană e nenulă, nu cât de înaltă e. „Prezent" = coloană nenulă, „absent" = coloană la zero.

De reținut

Vector caracteristic = doar prezență (0/1), nu numărul de apariții.
Test de apartenență în O(1) (car[x]); construire O(n), memorie O(V).
Folosește-l când contează doar „apare sau nu", nu „de câte ori".