Ștergerea din vector la BAC: deplasare și compactare

Ștergerea unui element dintr-un vector presupune deplasarea elementelor din dreapta lui cu o poziție spre stânga și reducerea lungimii logice. Capacitatea tabloului rămâne aceeași, dar programul va considera valabilă o porțiune mai scurtă. La BAC, contează să păstrezi ordinea elementelor rămase și să nu sari peste un element mutat.

Vom separa două cerințe: ștergerea unei poziții cunoscute și eliminarea tuturor elementelor care respectă o condiție. Prima se poate face prin deplasare. Pentru a doua, o compactare într-o singură parcurgere este adesea mai clară și mai eficientă. Această distincție apare frecvent în exercițiile de algoritmică din pregătirea pentru BAC.

Lungimea logică și capacitatea tabloului

Un tablou poate avea capacitatea de o mie de elemente, dar în problema curentă să fie folosite doar cinci. Lungimea logică este cinci. După ștergerea unui element, lungimea logică devine patru, chiar dacă memoria rezervată tabloului nu se micșorează.

Valoarea aflată dincolo de noua lungime nu mai face parte din vectorul relevant. Nu este obligatoriu să o înlocuiești cu zero. Este obligatoriu ca parcurgerile și afișarea să respecte noua lungime.

De exemplu, după ștergerea valorii de pe a doua poziție din secvența șapte, doi, nouă, patru, trei, partea validă trebuie să fie șapte, nouă, patru, trei. O valoare rămasă fizic în ultima celulă veche nu trebuie afișată.

Ștergerea unei poziții cunoscute

Presupunem că indicii încep de la zero și că indicele șters este valid. Fiecare element din dreapta lui se copiază în celula precedentă. Deplasarea se face de la stânga spre dreapta, începând cu locul care trebuie umplut.

Pentru vectorul șapte, doi, nouă, patru, trei și indicele unu, prima copiere pune nouă peste doi. A doua pune patru peste vechea poziție a lui nouă, iar a treia pune trei peste vechea poziție a lui patru.

Etapă	Partea memorată în cele cinci celule
Inițial	7, 2, 9, 4, 3
Prima copiere	7, 9, 9, 4, 3
A doua copiere	7, 9, 4, 4, 3
A treia copiere	7, 9, 4, 3, 3

După reducerea lungimii la patru, ultimul trei nu mai aparține porțiunii valide. Dublările temporare din tabel sunt normale: fiecare copiere umple o poziție, iar valoarea sursă poate rămâne până când este suprascrisă ulterior.

De ce direcția deplasării este importantă

La deplasarea spre stânga, citești din poziția următoare și scrii în poziția curentă. Parcurgerea crescătoare păstrează sursa pentru pasul următor. Dacă ai parcurge în sens invers, ai putea propaga aceeași valoare peste mai multe celule.

Pentru ștergerea ultimului element, nu există nimic de deplasat. Reduci doar lungimea. Pentru ștergerea primului element, deplasezi toate celelalte valori cu o poziție spre stânga.

Dacă vectorul conține un singur element și îl ștergi, rezultatul este un vector vid. Afișarea trebuie să respecte convenția cerută de problemă pentru acest caz. Nu accesa primul element după ștergere presupunând că el mai există logic.

Eliminarea tuturor valorilor negative prin compactare

În loc să ștergi separat fiecare valoare negativă, poți construi rezultatul în partea de început a aceluiași tablou. Un indice citește toate elementele inițiale, iar un contor arată câte elemente au fost păstrate.

Când valoarea curentă este nenegativă, o copiezi la prima poziție liberă a rezultatului și mărești contorul. Când este negativă, nu o copiezi. La final, contorul devine noua lungime.

Ordinea relativă a elementelor păstrate nu se schimbă, deoarece le întâlnești și le copiezi în aceeași ordine. Această proprietate se numește păstrarea stabilă a ordinii. Nu trebuie să sortezi valorile pentru a elimina elementele nedorite.

Program C++ complet

Programul citește între zero și o mie de numere întregi și elimină valorile negative. Zero este păstrat. Afișează noua lungime, apoi elementele rămase în ordinea inițială.

#include <iostream>
using namespace std;

int main() {
    int n, v[1000];
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> v[i];

    int k = 0;
    for (int i = 0; i < n; ++i) {
        if (v[i] >= 0) {
            v[k] = v[i];
            ++k;
        }
    }
    n = k;
    cout << n << '\n';
    for (int i = 0; i < n; ++i) {
        if (i > 0) cout << ' ';
        cout << v[i];
    }
    return 0;
}

Pentru secvența minus doi, cinci, minus trei, zero, șapte, rezultatul are lungimea trei și valorile cinci, zero, șapte. Pentru un șir format numai din valori negative, noua lungime este zero, iar a doua buclă de afișare nu execută niciun pas.

De ce nu suprascriem elemente necitite

La începutul fiecărui pas, numărul elementelor păstrate nu poate depăși numărul elementelor deja analizate. Prin urmare, poziția de scriere nu este în dreapta poziției de citire. Scrii fie în aceeași celulă, fie într-o celulă deja citită.

Astfel, copierea nu distruge o valoare care ar urma să fie analizată într-un pas viitor. Acesta este motivul pentru care compactarea poate fi făcută în același tablou, fără un al doilea vector.

După prelucrarea fiecărui prefix, primele poziții ale rezultatului conțin exact elementele acceptate din acel prefix, în ordinea inițială. La final, prefixul analizat este întregul vector, deci rezultatul este complet. Explicația leagă înțelegerea algoritmului de siguranța fiecărei copieri.

Capcana ștergerilor succesive

Dacă ștergi prin deplasare și apoi mărești imediat indicele, poți sări peste elementul care tocmai a ajuns în poziția curentă. Pentru două valori negative consecutive, prima este eliminată, iar a doua se mută în locul ei. Creșterea indicelui o lasă neverificată.

O soluție cu ștergeri repetate trebuie să reanalizeze poziția după o eliminare. Totuși, fiecare ștergere poate deplasa multe elemente, iar timpul poate deveni pătratic în lungimea șirului. Compactarea verifică fiecare element o singură dată și are timp liniar.

Memoria suplimentară a compactării este constantă: folosești doar câteva variabile pe lângă tabloul deja existent. Acest avantaj nu depinde de câte elemente sunt eliminate. Chiar dacă toate sunt păstrate, algoritmul continuă să funcționeze corect.

Exerciții cu răspunsuri

Șterge poziția a treia din patru, opt, unu, șase. În numerotarea de la unu, se elimină unu. Rezultatul este patru, opt, șase. Indicele folosit în convenția de la zero este doi.

Elimină valorile pare din doi, patru, cinci, șase, șapte. Rămân cinci și șapte. Primele două valori nedorite sunt consecutive, deci exemplul verifică dacă metoda cu ștergeri succesive sare peste una dintre ele.

Elimină valorile negative din zero, doi, trei. Vectorul rămâne neschimbat. Zero nu este negativ. Condiția de păstrare din program îl include corect.

Elimină toate elementele dintr-un vector cu un singur element. Noua lungime este zero. Nu afișa vechea valoare și nu folosi o buclă care presupune existența cel puțin a unei poziții valide.

Întrebări frecvente

Ștergerea înseamnă să pun zero în celulă?

Nu. Zero poate fi o valoare validă a vectorului. Ștergerea înseamnă eliminarea poziției din secvența logică, cu ajustarea elementelor și a lungimii.

Compactarea schimbă ordinea?

Varianta prezentată păstrează ordinea relativă a elementelor acceptate. Dacă ai folosi alte metode, precum înlocuirea cu ultimul element, această proprietate nu ar mai fi garantată.

Ce verific înainte de a considera soluția corectă?

Testează eliminarea primului și ultimului element, două eliminări consecutive, nicio eliminare și eliminarea tuturor valorilor. Pentru o analiză pe propriul cod, poți lucra cu un profesor de informatică.