Interclasare

interclas

h3. Indicatii de rezolvare

O prima solutie ar presupune citirea datelor intr-un acelasi sir si apoi sortarea acestuia. Complexitatea $O((N+M)log(N+M))$ nu este insa optima.

O prima solutie ar presupune citirea datelor intr-un acelasi sir si apoi sortarea acestuia. Complexitatea $O( (N+M) log(N+M) )$ nu este insa optima.

Abordarea problemei presupune interclasarea celor doua siruri, operatie ce are complexitatea $O(N+M)$. Vom parcurge sirurile $A$ si $B$ simultan, cu doi iteratori - $i$ si $j$. La fiecare pas vom introduce in sirul $C$ (cerut de problema) elementul minim dintre $A[i]$ si $B[j]$, avand grija ca iteratorii sa nu fi trecut de numarul de elemente din sir.

Abordarea problemei presupune interclasarea celor doua siruri, operatie ce are complexitatea O(N+M). Vom parcurge sirurile A si B simultan, cu doi iteratori - i si j. La fiecare pas vom introduce in sirul C (cerut de problema) elementul minim dintre A[i] si B[j], avand grija ca iteratorii sa nu fi trecut de numarul de elemente din sir.

Pentru exemplul problemei, primii pasi ai algoritmului pot fi urmatorii:
|_. Pas 1 |_. Pas 2 |_. Pas 3 |
|!problema/interclas?p1.JPG!

Introduc pe $A[i]$, deci $C = (1)$

Introduc pe A[i], deci C = (1)

|!problema/interclas?p2.JPG!

Introduc pe $B[j]$, deci $C = (1,2)$

Introduc pe B[j], deci C = (1,2)

|!problema/interclas?p3.JPG!

Introduc pe $A[i]$, deci $C = (1,2,3)$|

Introduc pe A[i], deci C = (1,2,3)|

Sursa de 100 de puncte se gaseste 'aici':http://infoarena.ro . De asemenea, o implementare mai scurta a algoritmului se poate gasi 'aici':http://infoarena.ro .