📦 Vectori

Capitolul 4 — Declarare, parcurgere, căutare, sortare, interclasare și probleme BAC

VectoriSortareCăutare binarăInterclasareCounting sort
📖 12 min
0
📋

Declararea și inițializarea vectorilor

🏠 Analogie: Vectorul = Bloc de apartamente

Gândeşte-te la un bloc cu N apartamente numerotate de la 1 la N. Fiecare apartament (element) are un număr de apartament (indicele) şi un chiriac (valoarea stocată). Calculatorul ştie exact unde e fiecare apartament fără să caute — acesta e accesul direct O(1).

  • 🔑 v[3] = apartamentul 3 → acces instant
  • 👥 Inserare la mijloc = toți chiriasii de la poziția k în sus se mută un etaj mai sus
  • 🗳 Ștergere = toți chiriasii de deasupra se coboară un etaj

Un vector (tablou unidimensional) este o colecție de elemente de același tip, stocate consecutiv în memorie, accesate prin indice.

// Declarare vector de n elemente întregi (maxim 100000)
int v[100001];  // indexat de la 0 la 100000
int n;          // numărul de elemente folosite efectiv

// Citire din tastatură
cin >> n;
for (int i = 1; i <= n; i++)  // indexare de la 1 (stil BAC)
    cin >> v[i];

// Inițializare cu 0 a întregului tablou
int a[100] = {0};       // toți cu 0
int b[] = {3, 1, 4, 1, 5};  // dimensiune dedusă automat: 5
La BAC, indexarea începe de obicei de la 1: v[1], v[2], ..., v[n]. Tabloul trebuie declarat cu dimensiunea n+1 cel puțin.
Acces: O(1)

v[i] — acces direct la elementul i, indiferent de n

Memorie: O(n)

n elemente × sizeof(tip) octeți consecutiv în RAM

🔁

Parcurgerea vectorilor — operații frecvente

Sumă, minim, maxim — O(n)

int suma = 0, minim = v[1], maxim = v[1];
int pozMin = 1, pozMax = 1;

for (int i = 1; i <= n; i++) {
    suma += v[i];
    if (v[i] < minim) { minim = v[i]; pozMin = i; }
    if (v[i] > maxim) { maxim = v[i]; pozMax = i; }
}

Afișare în ordine inversă

for (int i = n; i >= 1; i--)
    cout << v[i] << " ";

Număr de elemente pare

int nrPare = 0;
for (int i = 1; i <= n; i++)
    if (v[i] % 2 == 0) nrPare++;
cout << "Elemente pare: " << nrPare;

Verificare dacă vectorul este sortat crescător

bool sortat = true;
for (int i = 1; i < n; i++)
    if (v[i] > v[i+1]) { sortat = false; break; }
🔍

Căutare secvențială și binară

Căutare secvențială — O(n)

int cautareSecventiala(int v[], int n, int x) {
    for (int i = 1; i <= n; i++)
        if (v[i] == x) return i;  // returnează poziția
    return -1;  // nu a fost găsit
}
// Funcționează pe vector NESORTAT sau SORTAT
// Best: O(1)  Average: O(n/2)  Worst: O(n)

Căutare binară — O(log n) — doar pe vector SORTAT

int cautareBinara(int v[], int n, int x) {
    int st = 1, dr = n;
    while (st <= dr) {
        int mij = (st + dr) / 2;
        if (v[mij] == x) return mij;  // găsit!
        else if (v[mij] < x) st = mij + 1;  // x e în dreapta
        else dr = mij - 1;              // x e în stânga
    }
    return -1;
}
Trasare căutare binară — x=7, v=[1,3,5,7,9,11,13]:
Pas 1: st=1, dr=7, mij=4 → v[4]=7 → GĂSIT la poziția 4
Atenție la BAC: Dacă problema spune "vector sortat" → folosiți căutare binară O(log n). Pe vector nesortat → căutare secvențială O(n).
🎮 Demo interactiv — Linear vs Binary

Vectorul este generat sortat. Alege algoritmul și ținta, apoi compară numărul de pași.

Normal
Pași: 0
Setează ținta, alege Linear/Binary și apasă Start.
interval activ mij / element comparat găsit în afara intervalului
🔀

Sortarea vectorilor

Bubble Sort — cel mai cerut la BAC

void bubbleSort(int v[], int n) {
    for (int i = 1; i <= n-1; i++)
        for (int j = 1; j <= n-i; j++)
            if (v[j] > v[j+1])
                swap(v[j], v[j+1]);
    // O(n²) — bun pentru demonstrații, mai lent în practică
}

Selection Sort — explicat pas cu pas

void selectionSort(int v[], int n) {
    for (int i = 1; i <= n-1; i++) {
        int pozMin = i;
        for (int j = i+1; j <= n; j++)
            if (v[j] < v[pozMin]) pozMin = j;
        if (pozMin != i) swap(v[i], v[pozMin]);
    }
    // O(n²) în toate cazurile, O(1) spațiu
}

Insertion Sort — eficient pe date aproape sortate

void insertionSort(int v[], int n) {
    for (int i = 2; i <= n; i++) {
        int cheie = v[i], j = i - 1;
        while (j >= 1 && v[j] > cheie) {
            v[j+1] = v[j];
            j--;
        }
        v[j+1] = cheie;
    }
}

sort() din STL — O(n log n)

#include <algorithm>
sort(v + 1, v + n + 1);              // crescător (v indexat de la 1)
sort(v + 1, v + n + 1, greater<int>());  // descrescător
🎮 Demo interactiv — alege algoritmul

Compară Bubble, Selection și Insertion Sort vizual. Urmărește numărul de comparații și interschimbări.

Normal
Comparații: 0 Interschimbări: 0
Apasă Start.
nesortat comparat interschimbat pivot/min sortat
🔗

Interclasarea (Merge) a doi vectori sortați

Problemă: Dați doi vectori sortați A[1..m] și B[1..n]. Construiți vectorul C[1..m+n] care conține toate elementele, sortat. 
void interclasare(int a[], int m, int b[], int n, int c[]) {
    int i = 1, j = 1, k = 0;

    while (i <= m && j <= n) {
        if (a[i] <= b[j]) c[++k] = a[i++];
        else              c[++k] = b[j++];
    }
    // Copiem restul din A sau B
    while (i <= m) c[++k] = a[i++];
    while (j <= n) c[++k] = b[j++];
    // Complexitate: O(m+n) timp și spațiu
}
Exemplu:
A = [1, 3, 5, 7], B = [2, 4, 6]
C = [1, 2, 3, 4, 5, 6, 7] ✅
🎮 Demo interactiv — interclasare pas cu pas

Introdu valorile (vor fi sortate automat) și urmărește cum cei doi pointeri i și j construiesc rezultatul C.

Normal
Apasă Start pentru a interclasa cei doi vectori sortați.
element disponibil consumat plasat în C
✏️

Inserare și ștergere elemente

Inserare pe poziția p — O(n)

void insereaza(int v[], int &n, int p, int val) {
    // Deplasăm elementele de la p la n cu o poziție la dreapta
    for (int i = n; i >= p; i--)
        v[i+1] = v[i];
    v[p] = val;
    n++;
}

Ștergere de pe poziția p — O(n)

void sterge(int v[], int &n, int p) {
    // Deplasăm elementele de la p+1 la n cu o poziție la stânga
    for (int i = p; i < n; i++)
        v[i] = v[i+1];
    n--;
}
Complexitate: Inserarea/ștergerea la mijloc = O(n) din cauza deplasărilor. La capăt (stânga sau dreapta) poate fi O(1) dacă ne permitem structuri mai avansate.

📌 Exemplu pas cu pas — Inserare

Vector inițial: [3, 7, 1, 9, 4, 2], n = 6. Inserăm 99 pe poziția 3.
  1. v[6] = v[5] = 2  → [3, 7, 1, 9, 4, 2, 2]
  2. v[5] = v[4] = 4  → [3, 7, 1, 9, 4, 4, 2]
  3. v[4] = v[3] = 9  → [3, 7, 1, 9, 9, 4, 2]
  4. v[3] = v[2] = 1  → [3, 7, 1, 1, 9, 4, 2]
  5. v[3] = 99; n = 7  → [3, 7, 99, 1, 9, 4, 2]

⚠️ Bucla merge de la i = n spre p (descrescător), altfel suprascriem valori încă neutilizate.

📌 Exemplu pas cu pas — Ștergere

Vector inițial: [3, 7, 99, 1, 9, 4, 2], n = 7. Ștergem poziția 3 (valoarea 99).
  1. v[3] = v[4] = 1  → [3, 7, 1, 1, 9, 4, 2]
  2. v[4] = v[5] = 9  → [3, 7, 1, 9, 9, 4, 2]
  3. v[5] = v[6] = 4  → [3, 7, 1, 9, 4, 4, 2]
  4. v[6] = v[7] = 2  → [3, 7, 1, 9, 4, 2, 2]
  5. n = 6 (ignorăm „2" extra)  → [3, 7, 1, 9, 4, 2]

⚠️ Bucla merge de la p spre n − 1 (crescător). Decrementăm n la final.

🎮 Demo interactiv — Inserare & Ștergere pas cu pas

Vectorul are 6 elemente și capacitate 8. Alege o poziție, apoi apasă Inserează sau Șterge.

Normal
element curent deplasat rezultat final
💡 Truc BAC: Numărul de deplasări = n − p + 1 (inserare) sau n − p (ștergere). Cel mai rău caz: poziția 1 ⇒ n deplasări. Cel mai bun caz: poziția n+1 (final) ⇒ 0 deplasări.
📊

Vectori de frecvență (Counting Sort)

Când valorile sunt din domeniu mic [0, K], putem număra aparițiile în O(n+K).

int freq[1001] = {0};  // domeniu valori 0..1000

// Numărăm aparițiile
for (int i = 1; i <= n; i++)
    freq[v[i]]++;

// Afișăm valorile sortate (Counting Sort)
for (int val = 0; val <= 1000; val++)
    for (int j = 0; j < freq[val]; j++)
        cout << val << " ";

// Cel mai frecvent element
int maxFreq = 0, elMaxFreq = -1;
for (int i = 0; i <= 1000; i++)
    if (freq[i] > maxFreq) { maxFreq = freq[i]; elMaxFreq = i; }
Avantaj: Sortare în O(n+K) — mult mai rapid decât O(n log n) când K este mic. Ideal pentru note, cifre, vârste etc.

📌 Exemplu — frecvența cifrelor

Vector: v = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5], n = 11.
După parcurgere, freq[] arată așa:
cifră (i)0123456789
freq[i]0212131001
Sortat (Counting Sort): 1 1 2 3 3 4 5 5 5 6 9 ✅
Cel mai frecvent: 5 (apare de 3 ori).

📌 Exemplu — eliminarea duplicatelor în O(n)

// Afișează DOAR valorile distincte, în ordinea apariției
bool apar[1001] = {false};
for (int i = 1; i <= n; i++) {
    if (!apar[v[i]]) {
        cout << v[i] << " ";
        apar[v[i]] = true;
    }
}

📌 Exemplu — intersecția a două mulțimi

// Elementele comune între v[] (n elemente) și w[] (m elemente)
bool inV[1001] = {false};
for (int i = 1; i <= n; i++) inV[v[i]] = true;
for (int j = 1; j <= m; j++)
    if (inV[w[j]]) cout << w[j] << " ";
// O(n + m + K) în loc de O(n·m) naiv
🎮 Demo interactiv — Counting Sort pas cu pas

Introdu cifre 0..9 (separate prin spațiu sau virgulă). Faza 1 numără aparițiile, faza 2 reconstruiește vectorul sortat.

Normal
Vector sursă:
Vector de frecvență freq[]:
Ieșire sortată:
incrementăm tocmai mărit emis în output
Atenție la BAC: Vectorul de frecvență funcționează doar pentru valori întregi nenegative din domeniu mic. Pentru valori mari (ex. 10⁹) sau negative, ai nevoie de map<int,int> (clasa a XI-a) sau de redenumire (mapare la 0..K).
🧱

Demo Interactiv — Inserare, Ștergere, Căutare

Vectorul de mai jos are 8 sloturi (capacitate maximă). Sloturile goale sunt gri. Apasă butoanele pentru a vedea operațiile pas cu pas.

Normal
Apasă un buton pentru a vedea operația în acțiune.
Inserare: Poziție: Valoare:
Ștergere: Poziție: Căutare: Valoare:
Complexități de reținut:
  • Inserare la poziția k → mută n−k elemente la dreapta → O(n)
  • Ștergere de la poziția k → mută n−k elemente la stânga → O(n)
  • Căutare secvențială → parcurge tot vectorul în cel mai rău caz → O(n)
  • Acces direct v[i] → instant, nu depinde de n → O(1)
🧩

Probleme rezolvate — vectori

5 probleme clasice cu enunț, exemplu și soluție comentată. Încearcă întâi singur, apoi deschide soluția.

1 Maxim și poziția lui Ușor
Se citește un vector cu n elemente întregi (1 ≤ n ≤ 100). Afișează valoarea maximă și prima poziție pe care apare (indexare de la 1).
Intrare:
5
3 7 2 7 1
Ieșire:
7 2
💡 Vezi soluția 
#include <iostream>
using namespace std;
int v[105];
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i];
    int mx = v[1], poz = 1;
    for (int i = 2; i <= n; i++)
        if (v[i] > mx) { mx = v[i]; poz = i; }  // > strict ⇒ prima apariție
    cout << mx << " " << poz;
    return 0;
}

Idee: inițializăm cu primul element, parcurgem o singură dată. > strict (nu ≥) ⇒ păstrăm prima apariție. Complexitate O(n).

2 Numere prime din vector Ușor
Pentru un vector cu n elemente naturale (≤ 10⁶), afișează doar elementele care sunt numere prime, în ordinea apariției.
Intrare:
6
4 7 9 11 15 13
Ieșire:
7 11 13
💡 Vezi soluția 
#include <iostream>
using namespace std;
bool prim(int x) {
    if (x < 2) return false;
    for (int d = 2; d * d <= x; d++)
        if (x % d == 0) return false;
    return true;
}
int main() {
    int n, x; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        if (prim(x)) cout << x << " ";
    }
    return 0;
}

Idee: verificare prim până la √x (condiția d*d <= x evită sqrt()). Pentru valori mari sau apeluri repetate, pre-calculează un ciur.

3 Ștergerea duplicatelor (vector sortat) Mediu
Se dă un vector sortat crescător cu n elemente. Elimină duplicatele „in-place" și afișează vectorul rezultat și noua lungime.
Intrare:
7
1 1 2 3 3 3 5
Ieșire:
4
1 2 3 5
💡 Vezi soluția 
#include <iostream>
using namespace std;
int v[100005];
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i];

    int k = 1;                          // poziția unde scriem următorul element unic
    for (int i = 2; i <= n; i++)
        if (v[i] != v[k]) v[++k] = v[i];

    cout << k << "\n";
    for (int i = 1; i <= k; i++) cout << v[i] << " ";
    return 0;
}

Tehnică two-pointers: k arată ultima poziție validă, i scanează. Pentru că vectorul e sortat, duplicatele sunt vecine. Complexitate O(n), memorie O(1) suplimentară.

4 Cea mai lungă secvență crescătoare Mediu
Pentru un vector cu n elemente, găsește lungimea celei mai lungi secvențe strict crescătoare de elemente consecutive.
Intrare:
8
1 3 5 2 4 6 7 1
Ieșire:
4
💡 Vezi soluția 
#include <iostream>
using namespace std;
int main() {
    int n, x, prev = 0;
    cin >> n;
    int lung = 0, maxL = 0;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        if (i == 1 || x > prev) lung++;
        else lung = 1;          // rupt — pornim secvența nouă cu x
        if (lung > maxL) maxL = lung;
        prev = x;
    }
    cout << maxL;
    return 0;
}

Idee: ținem doar prev (elementul anterior) și lung (lungimea curentă). Nu e nevoie să stocăm tot vectorul. Complexitate O(n), memorie O(1).

Pe exemplu: 1<3<5 (3), apoi rupere; 2<4<6<7 (4), apoi rupere; 1 (1). Maxim = 4.

5 Suma maximă a unei subsecvențe (Kadane) Dificil
Se dă un vector cu n numere întregi (pot fi și negative). Găsește suma maximă a unei subsecvențe nevide de elemente consecutive.
Intrare:
9
-2 1 -3 4 -1 2 1 -5 4
Ieșire:
6
💡 Vezi soluția 
#include <iostream>
using namespace std;
int main() {
    int n, x;
    cin >> n;
    int sumaCur = 0, sumaMax;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        sumaCur = (i == 1) ? x : max(x, sumaCur + x);
        if (i == 1 || sumaCur > sumaMax) sumaMax = sumaCur;
    }
    cout << sumaMax;
    return 0;
}

Algoritm Kadane: pentru fiecare poziție, decidem dacă extindem subsecvența curentă (sumaCur + x) sau repornim de la x. Reținem maximul. Complexitate O(n).

Pe exemplu: subsecvența [4, -1, 2, 1] are suma 6.

💪 Vrei mai multă practică? Vezi quiz-ul de la finalul paginii (35 de întrebări) și problemele BAC din secțiunea următoare.
📝

Probleme tip BAC — vectori

Problemă 1 (BAC 2022): Se dă un vector cu n elemente întregi. Afișați elementele distincte în ordinea primei apariții.
Soluție: 
bool aparut[1001] = {false};
for (int i = 1; i <= n; i++) {
    if (!aparut[v[i]]) {
        cout << v[i] << " ";
        aparut[v[i]] = true;
    }
}
// O(n) timp, O(K) spațiu
Problemă 2: Dați un vector sortat cu n elemente. Eliminați duplicatele (păstrați câte una din fiecare valoare).
Soluție: 
int m = 1;  // noul n după eliminare
for (int i = 2; i <= n; i++)
    if (v[i] != v[i-1])
        v[++m] = v[i];
n = m;  // actualizăm dimensiunea
Problemă 3: Dați n și un vector v[1..n]. Verificați dacă vectorul este o permutare a lui {1, 2, ..., n}.
Soluție: 
int freq[100001] = {0};
bool ok = true;
for (int i = 1; i <= n; i++) {
    if (v[i] < 1 || v[i] > n || freq[v[i]] > 0) { ok = false; break; }
    freq[v[i]]++;
}
cout << (ok ? "DA" : "NU");
🔢

Ciurul lui Eratostene

🎯 Ce este Ciurul lui Eratostene?

Ciurul lui Eratostene este algoritmul clasic pentru a găsi toate numerele prime până la un număr dat N, în timp O(N log log N). Este unul dintre cei mai eficienți algoritmi pentru această problemă și apare frecvent la BAC.

Ideea: pornești de la 2, marchezi toți multiplii lui 2 ca neprimi, treci la 3, marchezi multiplii lui 3, și tot așa.

Implementare standard

#include <iostream>
using namespace std;

const int NMAX = 1000001;
bool ciur[NMAX];  // ciur[i] = true dacă i este NEPRIM

void genereazaCiur(int n) {
    ciur[0] = ciur[1] = true;  // 0 și 1 nu sunt prime
    for (int i = 2; (long long)i * i <= n; i++) {
        if (!ciur[i]) {             // i este prim
            for (int j = i * i; j <= n; j += i)  // pornim de la i²
                ciur[j] = true;   // multiplii lui i sunt neprimi
        }
    }
}

int main() {
    int n;
    cin >> n;
    genereazaCiur(n);
    for (int i = 2; i <= n; i++)
        if (!ciur[i]) cout << i << " ";
    return 0;
}
De ce pornim de la i² la pasul interior?
Toți multiplii mai mici decât i² (adică 2·i, 3·i, …, (i−1)·i) au fost deja marcați de pași anteriori. Astfel, evităm marcări duplicate și algoritmul este mai rapid.

Numărarea numerelor prime — problemă BAC frecventă

// Câte numere prime există în intervalul [a, b]?
genereazaCiur(b);
int cnt = 0;
for (int i = max(2, a); i <= b; i++)
    if (!ciur[i]) cnt++;
cout << cnt;

Verificare rapidă: este x prim?

// După apelul genereazaCiur(NMAX-1):
bool estePrim(int x) { return x >= 2 && !ciur[x]; }
Complexitate timp: O(N log log N)

Practic liniar pentru N ≤ 10⁶

Complexitate spațiu: O(N)

Un vector bool de N elemente ≈ 1 MB pentru N=10⁶

Atenție la BAC: Declarați ciur[] ca variabilă globală, nu în main(). Un vector de 10⁶ elemente declarat local provoacă stack overflow!
Exemplu — prime până la 20:
Start: toți false (neprimii vor fi marcați true)
Marchează multiplii lui 2: 4, 6, 8, 10, 12, 14, 16, 18, 20
Marchează multiplii lui 3: 9, 15 (6, 12, 18 deja marcate)
4² = 16 > 20 → stop
Prime găsite: 2, 3, 5, 7, 11, 13, 17, 19 ✅

📊 Ciur vs verificare divizori — de ce contează?

Pentru a verifica dacă un singur număr e prim, metoda cu divizori O(√x) e perfectă. Dar dacă trebuie să răspunzi la q întrebări de tipul „este x prim?", precalculul cu Ciur câștigă net:

Scenariu Divizori O(q·√N) Ciur O(N log log N + q) Câștigător
1 număr, N = 10⁶~1000 operații~10⁶ + 1 operațiiDivizori ✅
10⁴ numere, N = 10⁶~10⁷ operații~10⁶ + 10⁴ ≈ 10⁶Ciur ✅ (10×)
10⁵ numere, N = 10⁶~10⁸ operații (~ 1 s)~10⁶ (~ 10 ms)Ciur ✅ (100×)

🔧 Variante avansate ale Ciurului

a) Cel mai mic divizor prim (SPF)

În loc de bool, stocăm cel mai mic factor prim al fiecărui număr. Foarte util pentru a factoriza rapid orice x ≤ N:

int spf[NMAX];   // spf[i] = cel mai mic divizor prim al lui i
void construSPF(int n) {
    for (int i = 2; i <= n; i++) if (spf[i] == 0)
        for (int j = i; j <= n; j += i)
            if (spf[j] == 0) spf[j] = i;
}
// Factorizare în O(log x):
while (x > 1) { cout << spf[x] << " "; x /= spf[x]; }

b) Numărarea divizorilor cu Ciur

int nrDiv[NMAX] = {0};
for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i)
        nrDiv[j]++;
// nrDiv[12] = 6 (divizorii: 1,2,3,4,6,12)

Complexitate: O(N · H(N)) ≈ O(N log N), unde H(N) e seria armonică.

🎯 Probleme tipice BAC cu Ciur

  • Câte prime sunt în [a, b]? — precalculează ciur(b), apoi contează în O(b − a).
  • Sumă/produs de prime ≤ N — un singur for după ciur.
  • Cel mai mare prim ≤ N — iterează descendent.
  • Numere prime gemene (p și p+2 ambele prime) — verifică perechi consecutive.
  • Conjectura lui Goldbach — pentru orice n par ≥ 4, găsește p prim astfel încât n − p e tot prim.
  • Test rapid de primalitate pentru valori multiple — query în O(1) după precalcul.
🎮 Demo interactiv — Ciurul pas cu pas

Vezi cum sunt marcați multiplii fiecărui prim. Numerele tăiate sunt neprimi (compuse).

Normal
Prime găsite: —
Apasă Start pentru a porni ciurul.
prim curent multiplu tocmai marcat prim compus
💪

Exerciții interactive — testează cunoștințele