Étant donné un tableau arr[] composé de N entiers, la tâche consiste à trouver l’élément maximal avec la fréquence minimale.
Exemples:
Saisir: arr[] = {2, 2, 5, 50, 1}
Sortir: 50
Explication:
L’élément avec une fréquence minimale est {1, 5, 50}. L’élément maximum parmi ces éléments est de 50.
Saisir: arr[] = {3, 2, 5, 6, 1}
Sortir: 6
Approcher: Le problème donné peut être résolu en stockant la fréquence de l’élément du tableau dans un HashMap, puis en trouvant la valeur maximale ayant une fréquence minimale. Suivez l’étape ci-dessous pour résoudre le problème donné :
- Stockez la fréquence de chaque élément dans un HashMap, disons M.
- Initialisez deux variables, disons Valeur max comme INT_MIN et minFréq comme INT_MAX qui stocke l’élément maximum résultant et stocke la fréquence minimum parmi toutes les fréquences.
- Itérer sur la carte M et effectuez les étapes suivantes :
- Si la fréquence de l’élément courant est inférieure à minFréq puis mettre à jour la valeur de minFréq à la fréquence actuelle et à la valeur de Valeur max à l’élément courant.
- Si la fréquence de l’élément courant est égale à la minFréq et la valeur de Valeur max est inférieur à la valeur actuelle, puis mettez à jour la valeur de Valeur max à l’élément courant.
- Après avoir terminé les étapes ci-dessus, imprimez la valeur de Valeur max comme élément résultant.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++
|
#include en utilisant l’espace de noms std ; int maxElementWithMinFreq(int* arr, int N) { unordered_map pour (int i = 0; i < N; i++) { député[arr[i]]++; } int minFreq = INT_MAX; int maxValue = INT_MIN; pour (auto x : mp) { int num = x.premier; int freq = x.seconde; if (freq < minFreq) { minFreq = freq; valeurmax = nombre ; } else if (freq == minFreq && Valeurmax < num) { valeurmax = nombre ; } } renvoyer maxValue ; } int main() { int arr[] = { 2, 2, 5, 50, 1 } ; int N = taillede(arr) / taillede(arr[0]); cout << maxElementWithMinFreq(arr, N); renvoie 0 ; } |
Complexité temporelle : AU)
Espace auxiliaire : AU)
Attention lecteur ! N’arrêtez pas d’apprendre maintenant. Obtenez tous les concepts importants de DSA avec le Cours auto-rythmé DSA à un prix adapté aux étudiants et devenez prêt pour l’industrie. Pour compléter votre préparation de l’apprentissage d’une langue à DS Algo et bien d’autres, veuillez vous référer Cours complet de préparation aux entretiens.
Au cas où vous souhaiteriez assister cours en direct avec des experts, veuillez vous référer Cours en direct DSA pour les professionnels en activité et Programmation compétitive en direct pour les étudiants.
