Selectarea elementelor unice de matrice
Sarcină - este necesar să selectați toate elementele unice dintr-o matrice neordonată de elemente. Să complicăm sarcina după cum urmează - să încercați să nu folosiți memorie suplimentară și să puneți elemente unice în matricea curentă.
Cel mai simplu algoritm este de a lua un element și de ao compara cu toate. Pentru lucru avem nevoie de două contoare, primul omite toate elementele în ordine, al doilea ocolește toate elementele și le compară cu cel curent.
Rețineți că variabilele sunt întotdeauna nonnegative. Acest lucru va duce la unele particularități.
Acum, dacă schimbăm matricea și lăsăm în ea numai elemente diferite, mărimea acesteia se va schimba (înțelegem numărul de elemente diferite aici, nu vom schimba dimensiunea reală), astfel încât dimensiunea inițială a matricei este trecută prin pointer. Același pointer va stoca numărul de elemente după conversie.
Esența algoritmului: luăm elementul și vedem dacă el a avut aceleași elemente înaintea lui. Dacă nu, atunci copiați acest element, dacă există, apoi mergeți la elementul următor. Pentru a copia, introduceți poza contra - numărul de elemente deja existente ale matricei.
și steagul unic, indicând faptul că elementul curent nu se potrivește cu nici unul dintre cele deja prezente în matrice.
Ciclul de verificare în sine
Pentru o buclă într-o buclă, complexitatea va fi de ordinul n 2. Acest algoritm păstrează ordinea elementelor. Pentru rețele de dimensiuni mici, acest algoritm va fi mai rapid decât altele, având în vedere simplitatea.
Există și algoritmi mai rapizi. Dacă luați o matrice ordonată, atunci în ea aceleași elemente se află una lângă cealaltă. Puteți lua variabila prev, care stochează valoarea anterioară a elementului matricei. Dacă elementul curent este prev, apoi sări peste, dacă nu, apoi copiați și modificați valoarea precedentului la valoarea elementului curent.
Deoarece vom folosi sortarea rapidă standard, vom avea nevoie și de dimensiunea unui element și de funcția de comparare a elementelor.
Algoritmul petrece o medie de n ∙ log (n) pentru sortare + o trecere prin matrice (încă n), adică complexitatea ordinii n + n ∙ log (n). Cu toate acestea, trebuie să vă amintiți că sortarea rapidă pentru magistralele mici este ineficientă, astfel încât pentru rețelele mici acest algoritm va funcționa mai lent decât quadratic.
Metode bazate pe calcul
Dacă puterea unui set de elemente este mică (puține elemente diferite), atunci este posibil să numărați numărul de apariții. Acest lucru este deosebit de convenabil atunci când toate elementele posibile sunt cunoscute în avans. De exemplu, trebuie să găsiți toate literele diferite din cuvânt. Deoarece numărul de caractere diferite (în cazul nostru) nu este mai mare de 256, atunci putem crea o matrice de 256 elemente egale cu zero.
Utilizăm codul numeric al simbolului ca indice al matricei și mărim valoarea elementului corespunzător.
Atunci când elementele unui set nu sunt cunoscute, ele folosesc de obicei o structură de date specializată care vă permite să adăugați rapid elemente și să verificați aparițiile, de exemplu, un dicționar. o matrice hashed sau o matrice hashed asociative.
ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 [email protected] Ștefan Șpașev studenți
Articole similare
Trimiteți-le prietenilor: