Eliminarea duplicatelor dintr-un vector sortat C++

Din vectorul sortat 1 1 3 3 3 8 vrem să obținem 1 3 8. Nu ștergem repetat câte o poziție, deoarece fiecare ștergere ar muta alte elemente. Construim rezultatul în prima parte a aceluiași tablou, cu un indice pentru citire și unul pentru scriere.

Sortarea este o condiție a problemei

Citim 0≤n≤1000 și n întregi sortați nedescrescător. Afișăm numărul k al valorilor distincte și, pe linia următoare, cele k valori. Pentru n=0, a doua linie este goală. Valorile egale sunt alăturate tocmai datorită sortării.

În 1 3 1, simpla comparație cu ultima valoare păstrată nu elimină ultima apariție a lui 1. Dacă intrarea nu este sortată și trebuie păstrată ordinea inițială, aceasta este altă problemă. Nu adăuga sortare fără să verifici dacă ordinea are semnificație.

Prefixul construit are lungimea k

La început k=0, deci rezultatul este gol. Pentru fiecare a[i], îl păstrăm dacă nu avem încă niciun element sau dacă diferă de a[k-1], ultima valoare din rezultat. Scriem noua valoare în a[k] și apoi mărim k.

Pe exemplu, primul 1 este scris în a[0]. Al doilea este ignorat. Primul 3 ajunge în a[1], următoarele copii sunt ignorate, iar 8 ajunge în a[2]. La final k=3. Celulele dincolo de k pot conține date vechi; ele nu mai fac parte din rezultatul logic.

Din 1,1,3,3,3,8 păstrăm prima apariție a fiecărui grup: 1,3,8. Dimensiunea logică devine 3.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    int a[1000];
    for(int i=0;i<n;++i) cin >> a[i];
    int k=0;
    for(int i=0;i<n;++i) if(k==0 || a[i]!=a[k-1]) a[k++]=a[i];
    cout << k << '\n';
    for(int i=0;i<k;++i) cout << (i?" ":"") << a[i];
    cout << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;++i) cin >> a[i];
    int k=0;
    for(int i=0;i<n;++i) if(k==0 || a[i]!=a[k-1]) a[k++]=a[i];
    cout << k << '\n';
    for(int i=0;i<k;++i) cout << (i?" ":"") << a[i];
    cout << '\n';
}

De ce nu stricăm date necitite

În orice moment k≤i+1. Înaintea unei scrieri, k≤i, deci scriem pe poziția curentă sau mai la stânga, niciodată peste o valoare încă necitită. Acest fapt justifică folosirea aceluiași tablou pentru intrare și rezultat.

Operatorul ||, adică „sau”, verifică întâi k==0. Când aceasta este adevărată, expresia a[k-1] nu mai este evaluată; evităm astfel indicele -1. Indicii utili ai rezultatului sunt 0..k-1, capacitatea tabloului clasic rămânând 1000. În varianta vector, nu micșorăm obiectul: și acolo afișăm numai prefixul k.

Timpul este O(n), o singură parcurgere. Folosim O(1) memorie suplimentară, deoarece nu declarăm un al doilea tablou. Datele de intrare ocupă separat O(n) memorie în varianta vector.

Exersează

Pentru 2 2 2 obții o singură valoare 2. Pentru -2 0 5 nu elimini nimic. Verifică n=0 și n=1, apoi explică de ce ignorarea elementelor nu cere mutarea întregii părți din dreapta.

Revezi ștergerea din vector, sortarea și indicii și capacitatea.

Întrebări frecvente

Cum elimin duplicatele dintr-un vector sortat fără ștergeri repetate?

Parcurge elementele și scrie fiecare valoare nouă în prefixul rezultat. Un indice citește datele, altul numără valorile distincte. Algoritmul are timp O(n).

De ce este necesară sortarea pentru compactarea duplicatelor?

Sortarea face ca toate aparițiile aceleiași valori să fie consecutive. Fără această proprietate, compararea numai cu ultima valoare păstrată nu elimină repetările aflate în grupuri diferite.

După compactare se schimbă capacitatea tabloului clasic?

Nu. Se schimbă dimensiunea logică: numai primele k poziții reprezintă rezultatul. Celulele rămase există fizic, dar nu trebuie afișate sau tratate ca valori ale vectorului compactat.