Problema cu vector de secventa C++

Limbaje de Programare
1

Cerinta: din fisier se citesc maxim 10^6 numere naturale.Aflati cifrele care apar in aceste numere si afisati-le in ordinea crescatoare a numarului de aparitii.Ex: numerele: 124 229 1322 4 534
Rezultat: 5 9 1 3 4 2
//(cifra 5 apare cel mai putin iar cifra 2 apare cel mai mult)

Ce am facut pana acum:am utilizat un vector de frecventa ca sa aflu de cate ori apare fiecare cifra.

int n,v[10]={0},c; // cu f citesc din fisier(asta e mai putin important)
while(f>>n) {
  while(n) {
   c=n%10;
  v[c]++; // iau fiecare cifra si incrementez acea pozitie in vector
  n=n/10;
    }
}

Acum problema e sortarea,vectorul are numarul pe aparitii a fiecarei cifre(pe pozitia 5 se afla numarul de aparitii a cifrei 5 etc)
Daca ma apuc sa le sortez crescator se schimba numerele si se pierd fata de indici ca sa zic asa(numarul de aparitii a cifrei 5 va pleca de pe pozitia 5).Aici e problema si nu stiu cum sa rezolv!

//probleme asemanatoare sunt cele unde se da un vector nesortat si se cere sa se sorteze iar apoi sa se afiseze pe rand fiecare element si pozitia pe care era initial(inainte sa fie sortat)

2

Poti folosi structuri / clase?

Daca da, ai putea sa-ti faci o structura / clasa cu doua campuri: Cifra si Frecventa; apoi folosesti un vector de asemenea obiecte, pe care-l populezi cu ce obtii din codul pe care l-ai scris; si apoi sortezi acest vector in functie de campurile Frecventa.

3

nu
in schimb pot folosi functii

4

Ceva foarte eficient nu-mi vine in minte.

Ai putea sa faci o functie care sa-ti zica cifra cu frecventa minima din vector. Sa zicem ca ti-ar intoarce o variabila cfm. Creezi un al doilea vector in care sa pui cifrele ordonate dupa frecventa, ordered. Faci ordered[0] = cfm, apoi v[cfm] = -1, apoi chemi iar functia care sa-ti dea cifra cu frecventa minima, avand grija sa nu iei in considerare valorile negative; cifra pe care o pui in ordered[1] si tot asa…

2 Likes
5

Nu trebuie decat sa ai si un vector cu indici si sa sortezi ambii vectori simultan, adica atunci cand sortezi dupa valoarea frecventei sa muti si indicii la fel ca frecventele.

O alternativa ceva mai simpla: poti sa pui atat frecventa cat si indicele in std::pair si sa folosesti std::sort pe un vector cu asemenea elemente. in first pui frecventa, in second pui indicele.

2 Likes