Am o noua problema care trebuie rezolvata cat mai optim.
Problema e simpla, insa nu stiu daca e cea mai optima solutie.
„Sa se scrie o functie care sa decida daca 2 siruri de numere sunt sau nu anagrame (fiecare numar din primul sir sa se regaseasca in al 2-lea sir).”
Eu m-am gandit sa sortez ambele siruri dupa care sa fac o singura parcurgere pe ambele siruri deodata.
Stiti vreo solutie mai optima din punct de vedere al timpului si a memoriei?
Poti folosi un algoritm inspirat din counting sort, in O(n).
Tii 2 vectori de intregi V1 si V2 (initial ambii vectori contin doar valori egale cu 0).
Construiesti vectorul V1 astfel:
V1[0] -> tine de cate ori apare cifra 0 in sirul 1
V1[1] -> tine de cate ori apare cifra 1 in sirul 1
…
V1[9] -> tine de cate ori apare cifra 9 in sirul 1
Pentru asta, folosesti un algoritm simplu:
pentru fiecare cifra din sirul 1:
V1[cifra]++;
Similar, contruiesti vectorul V2, pentru sirul 2
Apoi compari cei 2 vectori intr-o singura trecere.
dar asta din cate inteleg eu merge doar daca ai un sir de cifre.
eu insa am numere.
sir1: 2 34 72 29 13
sir2: 34 13 29 2 72
si in cazul asta sunt anagrame. dar daca as avea elementele 12 si 2 in primul sir si 1 si 22 in al 2-lea sir dupa algoritmul de mai sus mi-ar da ca sunt tot anagrame.
Daca ai siruri de intregi, ai mai multe solutii:
1. Poti folosi o structura de date de tip dictionar.
Parcurgi primul sir si adaugi fiecare numar in dictionar.
Parcurgi al doilea sir si cauti fiecare numar din el in dictionar.
Pentru a implementa structura de date poti folosi o tabela de dispersie, de exemplu.
2. Daca vrei o solutie simpla, sortezi cele doua siruri si le compari intr-o singura parcurgere.
asa ceva mi s-a mai zis si in alta parte. sa folosesc hash-uri, care sunt tot ca si tabelele de dispersie din cate am inteles eu.
insa nu le stiu folosi.
daca aveti vreun algoritm implementat cu asa ceva mi-ar prinde bine ca sa inteleg cum functioneaza.
Pagina de pe wikipedia este foarte buna:
Uita-te peste:
hash-table.h
hash-table.c
hash-int.h
hash-int.c
Un exemplu de utilizare:
Atat hashtable-ul cat si counting-sort sunt mare consumatoare de memorie. Problema asta e clasica… se rezolva cu radix-sort.