k cele mai frecvente elemente dintr-un vector (make_pair intrebare)

#1
tutuN_

Posted 07 August 2021 - 18:51

Junior Member

Grup: Members
Posts: 137
Înscris: 21.09.2014

Salut, am de rezolvat o problema in care primesc ca input un vector de numere intregi si un intreg k. Trebuie sa returnez un vector cu k cele mai frecvente elemente din vector.

Ex:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Solutia mea:

vector<int> topKFrequent(vector<int>& nums, int k) {
	 unordered_map<int, int> mp;
	 priority_queue<pair<int, int>> pq;
	 vector<int> res;
	
	 for(auto it: nums) {
		 mp[it]++;
	 }
	
	 for(auto it: mp) {
		 pq.push(make_pair(it.second, it.first));
	 }
	 for(int i=0; i<k; i++) {
		 res.push_back(pq.top().second);
		 pq.pop();
	 }
	 return res;
		
	
}

Am folosit o tabela de dispersie, bag numerele in ea, apoi folosesc o coada de prioritate in care bag perechile key->value din tabela de dispersie.

Confuzia mea e la linia

pq.push(make_pair(it.second, it.first));

Initial am scris

pq.push(make_pair(it.first, it.second));

Sa fie primul element din pereche elementul in sine, iar al doilea sa fie frecventa acestuia, doar ca atunci cand mi le baga in coada de prioritate, nu mi le baga in ordine. Adica pq.top() n-o sa fie elementul cu frecventa cea mai mare. In schimb, daca scriu cum am scris solutie, mi le baga in mod corect in coada. pq[0] e perechea cu elementul si frecventa cea mai mare.

De ce se intampla asta?
Mersi!

Edited by tutuN_, 07 August 2021 - 18:52.

Back to top

#2
sftpdt

Posted 07 August 2021 - 21:36

Senior Member

Grup: Senior Members
Posts: 3,673
Înscris: 29.08.2013

Pai first, second ce reprezinta?
https://www.cplusplu.../unordered_map/

Quote

Iterators to elements of unordered_map containers access to both the key and the mapped value. For this, the class defines what is called its value_type, which is a pair class with its first value corresponding to the const version of the key type (template parameter Key) and its second value corresponding to the mapped value (template parameter T):

Practic, initial ti le sorta dupa valoare, nu dupa numarul de aparitii.

Back to top

#3
YalFa

Posted 08 August 2021 - 18:10

Member

Grup: Members
Posts: 618
Înscris: 02.05.2020

Poti face si fara map-uri.
Ordonezi crescator vectorul si cu doua variabile tii minte elemetul respectiv si frecventa sa de aparitiei.
Daca dai de un alt element cu o frecventa mai mare , inlocuiesti continutul frecventei.
La iesire din bucla , vei avea elementul si frecventa cea mai mare.

Back to top

#4
TS030

Posted 25 August 2021 - 12:51

Guru Member

Grup: Senior Members
Posts: 15,193
Înscris: 25.06.2012

Și nu rezolvi nimic cu asta, c�ci ai nevoie de k cele mai frecvente elemente.

Eu sunt curios de ce a ales OP priority_queue.

Back to top

Anunturi

Chirurgia cranio-cerebrală minim invazivă

Tehnicile minim invazive impun utilizarea unei tehnologii ultramoderne.

Endoscoapele operatorii de diverse tipuri, microscopul operator dedicat, neuronavigația, neuroelectrofiziologia, tehnicile avansate de anestezie, chirurgia cu pacientul treaz reprezintă armamentarium fără de care neurochirurgia prin "gaura cheii" nu ar fi posibilă. Folosind tehnicile de mai sus, tratăm un spectru larg de patologii cranio-cerebrale.

www.neurohope.ro

k cele mai frecvente elemente dintr-un vector (make_pair intrebare)

#1 tutuN_ Posted 07 August 2021 - 18:51

#2 sftpdt Posted 07 August 2021 - 21:36

#3 YalFa Posted 08 August 2021 - 18:10

#4 TS030 Posted 25 August 2021 - 12:51

Anunturi

▶ 0 user(s) are reading this topic

Sign In

#1
tutuN_

Posted 07 August 2021 - 18:51

#2
sftpdt

Posted 07 August 2021 - 21:36

#3
YalFa

Posted 08 August 2021 - 18:10

#4
TS030

Posted 25 August 2021 - 12:51