Prelucrări pe vectori

Minim, maxim, sume, frecvențe, ștergere și inserare, adică tiparele scurte din care se compun problemele mari.

Parcurgerea, care le conține pe toate

Aproape tot ce se face cu un vector are aceeași formă:

for (int i = 1; i <= n; i++) {
    // ceva cu v[i]
}

Diferă doar ce pui în corp și ce pregătești înainte. Mai jos sunt tiparele care apar cel mai des.

Sumă, produs, medie

long long suma = 0;
for (int i = 1; i <= n; i++)
    suma += v[i];
double media = (double)suma / n;

Acumulatorul se inițializează cu 0 pentru sumă și cu 1 pentru produs. Suma se declară long long, pentru că o mie de valori de ordinul milioanelor depășesc un int.

Cu condiție, se schimbă doar corpul:

long long suma = 0;
int cate = 0;
for (int i = 1; i <= n; i++)
    if (v[i] % 2 == 0) {
        suma += v[i];
        cate++;
    }

Dacă vrei media elementelor pare, ai nevoie și de cate, și de un test cate > 0 înainte de împărțire.

Minim și maxim

int maxim = v[1];
for (int i = 2; i <= n; i++)
    if (v[i] > maxim)
        maxim = v[i];

Inițializează cu primul element, nu cu 0. Dacă vectorul conține numai numere negative, un maxim pornit de la 0 rămâne 0, o valoare care nu există în date.

Dacă îți trebuie și poziția:

int poz = 1;
for (int i = 2; i <= n; i++)
    if (v[i] > v[poz])
        poz = i;
// v[poz] este maximul, poz este poziția lui

Dacă reții poziția în loc de valoare, le ai pe amândouă. Cu > strict se reține prima apariție a maximului, iar cu >= ultima. Unele enunțuri cer explicit una dintre ele.

Al doilea maxim

O întrebare clasică. Varianta greșită este să afli maximul, să-l ștergi și să reiei. Varianta bună ține două valori deodată:

int m1 = v[1], m2 = -2000000000;
for (int i = 2; i <= n; i++) {
    if (v[i] > m1) {
        m2 = m1;      // fostul maxim coboară pe locul doi
        m1 = v[i];
    } else if (v[i] > m2 && v[i] != m1) {
        m2 = v[i];
    }
}

Ordinea din primul if este esențială: m2 primește vechea valoare a lui m1 înainte ca m1 să se schimbe.

Numărare și frecvențe

Când doar numeri câte elemente au o proprietate, e simplu. Când vrei să știi de câte ori apare fiecare valoare, folosești un al doilea vector, indexat chiar după valoare:

int fr[1001] = {0};
for (int i = 1; i <= n; i++)
    fr[v[i]]++;

fr[x] spune de câte ori apare x. Ideea e foarte puternică, pentru că transformă căutarea într-o simplă citire. Are însă două condiții.

Valorile trebuie să fie întregi și mărginite. fr trebuie declarat cel puțin cât valoarea maximă posibilă plus unu. Dacă valorile ajung la 10⁹, nu merge.

Valorile trebuie să fie nenegative, altfel indicele iese din vector. Pentru valori negative se decalează: fr[v[i] + 1000].

Cu vectorul de frecvențe, multe întrebări devin banale:

// valoarea care apare de cele mai multe ori
int best = 0;
for (int x = 0; x <= 1000; x++)
    if (fr[x] > fr[best]) best = x;

// câte valori distincte
int distincte = 0;
for (int x = 0; x <= 1000; x++)
    if (fr[x] > 0) distincte++;

// prima valoare care apare o singură dată
for (int i = 1; i <= n; i++)
    if (fr[v[i]] == 1) { cout << v[i]; break; }

Ștergerea unui element

Un vector nu are „găuri". Ca să ștergi elementul de pe poziția p, muți totul cu o poziție la stânga și micșorezi n:

for (int i = p; i < n; i++)
    v[i] = v[i+1];
n--;

Bucla merge înainte, de la p spre n. Ordinea contează: dacă ai merge invers, ai suprascrie valori pe care încă nu le-ai mutat.

Inserarea unui element

Invers: faci loc mutând spre dreapta, pornind de la coadă.

for (int i = n; i >= p; i--)
    v[i+1] = v[i];
v[p] = x;
n++;

Aici bucla merge înapoi, de la n spre p. Și aici, în ordinea cealaltă datele s-ar strica.

Ține minte: la ștergere mergi înainte, la inserare mergi înapoi.

Ștergerea tuturor elementelor cu o proprietate

Dacă ștergi unul câte unul, faci multă muncă degeaba. Mai bine reconstruiești vectorul dintr-o singură parcurgere:

int k = 0;
for (int i = 1; i <= n; i++)
    if (v[i] % 2 != 0)        // păstrez doar impare
        v[++k] = v[i];
n = k;

k numără câte elemente s-au păstrat până acum și arată unde se scrie următorul. Cum k rămâne mereu în urma lui i, nu suprascriem nimic necitit.

Merită să reții tiparul acesta, cu două indexuri, unul care citește și unul care scrie. Rezolvă ștergerea, eliminarea duplicatelor și filtrarea, toate în n pași.

Răsturnarea

for (int i = 1, j = n; i < j; i++, j--) {
    int aux = v[i];
    v[i] = v[j];
    v[j] = aux;
}

Condiția este i < j, nu i <= j. Cu <=, la un vector de lungime impară elementul din mijloc s-ar interschimba cu el însuși, ceea ce e inofensiv, dar inutil. Mai grav, o buclă până la n ar interschimba totul de două ori și ar readuce vectorul la forma inițială.

De reținut

Maximul se inițializează cu primul element, nu cu 0.
Dacă reții poziția în loc de valoare, ai și valoarea, și poziția.
Vectorul de frecvențe indexat după valoare rezolvă multe probleme dintr-o parcurgere, dar cere valori întregi, nenegative și mărginite.
Ștergere: mută la stânga, mergi înainte. Inserare: mută la dreapta, mergi înapoi.
Filtrarea se face cu doi indici, unul de citire și unul de scriere.