Question

Salut!

Problema 3798 NrMinMaxAp de pe pbinfo


Scrieți funcția care are antetul: int NrMinMaxAp(vector &a)

Funcția va returna numărul care apare de cele mai multe ori în a. Dacă există mai multe numere care apar de număr maxim de ori, se va returna minimul dintre ele.



Ideea e ca nu stiu exact cum sa parcurg acel vector (nu am invatat iteratori)

Cam asta am scris pana acum:


int NrMinMaxAp(vector &a)

{

int i,M=0,x,n,f;

unordered_map m;
n=a.end(); f=a.begin();
for (i=f; i != n; i++)

m[a[i]]++;


for (auto e: m)

if (e.second>=M)

{

M=e.second;

if (x>e.first) x=e.first;

}


return x;

}

doar ca imi da eroare...ajutor pls:(((

(raspunsurile la misto se raporteaza)

Answer 1

1. Oleacă despre librăriile astea

1.1. Template-uri

(introducere în comentariu)

Adică clasa pentru un vector a fost implementată pentru a putea fi folosită cu orice tip de date, și în funcție de cum inst-anțiezi tu obiectul, pre-procesorul de la compilator va completa și genera el clasele în spate.

Adică dacă tu vei scrie

vector<int> k

Ți se va inst-anția un obiect de tip vector care va putea stoca int-uri. Dacă faci același lucru cu un char, sau chiar cu o structură proprie, se va face același lucru dar va stoca exact tipul transmis de tine. Asta este numaidecât necesar ca să știe clasa de vector cât spațiu să aloce. Adică dacă tu vrei să stochezi int-uri, va trebui să aloce câte 4 bytes pentru fiecare element (adică un sizeof(int)).

În spate, un template de genul arată astfel (aici e doar o funcție ca exemplu):

template <typename T>

T max_of(T x, T y) {

cout<<sizeof(T);

return x > y ? x : y;

}

Iar tu dacă vei scrie în codul tău:

cout<<max_of<short>(3, 7);

cout<<max_of<double>(3.3, 7.0);

cout<<max_of<short>(1, 13);

Înainte de compilare, în spate se va genera exact codul următor:

short max_of(short x, short y) {

cout<<sizeof(short);

return x > y ? x : y;

}

double max_of(double x, double y) {

cout<<sizeof(double);

return x > y ? x : y;

}

Și prima funcție generată se va apela pentru primul și al treilea cout, iar a doua pentru al doilea cout.

1.2. Librăria vector

Sunt convins că știi deja cum funcționează librăria, dar aș vrea să avem și asta scris aici, don't mind me. =))

Vector-ul e o clasă din STL (din librăria <vector>) ce îți administrează practic un array de date de tipul pe care-l vrei tu. Acum, chiar și în lipsa iteratorilor, pe vector se pot efectua o mulțime de operații simple (cod și în figura 1):

vector<int> g1; // declarăm un vector cu elemente int

g1.push_back(5); // adăugăm în vector la sfârșit numărul 5

g1.push_back(10);

g1.push_back(15);

cout<<g1[0]<<endl; // afișăm elementul 0 din vector

cout<<g1.size()<<endl; // afișăm dimensiunea vectorului

// Iterăm prin vector:

for(int i = 0; i < g1.size(); i++) {

cout<<g1[i]<<" "; // sau cout<<g1.at(i);

}

1.3. Librăria map

Clasa map din librăria <map> folosește tot un template, însă are nevoie de 2 tipuri de date, nu doar de unul cum e cazul pentru vector. De ce? Pentru că el stochează datele ca într-un fel de mapă/index de valori, adică primul tip e cheia, al doilea e valoarea.

Și ca să intrăm direct în brânză, să luăm un exemplu: să zicem că putem avea 3 clase de a 9-a (9A, 9B, 9C), și fiecare poate avea un anume număr de elev. Pentru a stoca o astfel de chestie într-un map, avem nevoie de o cheie reprezentată de un caracter (care va fi litera) și valoarea reprezentată de un int (care va fi numărul de elevi). Codul (și în figura 2):

map<char, int> clase;

clase['A'] = 33;

clase['B'] = 22;

clase['C'] = 28;

cout<<clase['B'];

1.4. Iteratori

În timp ce iteratorii nu sunt o necesitate absolută pentru vectori, având template-uri cu clase ce pot stoca o sumedenie de ciudățenii, iterarea prin ele devine oleacă mai complicată, așadar s-a inventat o șmecherie care e similară cu... să zicem iterarea printr-un șir de caractere (dacă ai mai lucrat cu pointeri). Să presupunem că avem un șir de caractere

char s[] = "ana";

Acesta va conține pe rând, pe primele 4 poziții, următoarele chestii: 'a', 'n', 'a' și NULL.

Noi dacă primim un pointer spre prima poziție, cum am pute itera prin litere? Uite exact așa (figura 3):

char* p = s; // punem în p adresa spre prima literă ('a')

for(char* q = p; *q != NULL; q++) {

cout<<"caracter: "<<*q;

}

//// o să dea un warning la null-ul ăla, dar lasă-l așa, nu e așa important =))

Acum, cum funcționează un iterator printr-un vector? Să facem asta pentru exemplul nostru anterior de vector:

g1.begin() ne dă un fel de pointer (adică iteratorul) cu adresa spre primul element din g1

g1.end() ne dă un fel de pointer (adică iteratorul) cu adresa după ultimul element (adică să validăm că dacă am ajuns aici, ne oprim)

Deci codul ar arăta așa (figura 4):

vector<int>::iterator it; // ne declarăm iteratorul

for(it = g1.begin(); it != g1.end(); it++) {

cout<<*it<<endl; // accesăm iteratorul

}

Practic la început punem în it adresa spre primul element, apoi la condiție ne asigurăm că n-am ajuns la sfârșit, și după fiecare iterație facem it++ (adică va crește adresa exact cu dimensiunea elementului, magia pointerilor). Iar în interior facem exact ce facem cu orice pointer ca să ajungem la valoarea de la adresă, punem steluța.

Bun, dar cum facem asta la map? Easy peasy (tot figura 4):

map<char, int>::iterator it2; // ne declarăm iteratorul

for(it2 = clase.begin(); it2 != clase.end(); it2++) {

// accesăm cheia

cout<<"clasa "<<(*it2).first<<": ";

// sau cout<<"clasa "<<it2->first<<": ";

// accesăm valoarea

cout<<(*it2).second<<" elevi"<<endl;

// sau cout<<it2->second<<" elevi"<<endl;

}

1.5. Iterație cu auto

(comentariu)

2. Rezolvare

(figura 5)