Dada una array arr[] que consta de N enteros, la tarea es encontrar el elemento máximo con la frecuencia mínima .
Ejemplos:
Entrada: arr[] = {2, 2, 5, 50, 1}
Salida: 50
Explicación:
El elemento con frecuencia mínima es {1, 5, 50}. El elemento máximo entre estos elementos es 50.Entrada: arr[] = {3, 2, 5, 6, 1}
Salida: 6
Enfoque: el problema dado se puede resolver almacenando la frecuencia del elemento de array en un HashMap y luego encontrar el valor máximo que tiene una frecuencia mínima. Siga el siguiente paso para resolver el problema dado:
- Almacene la frecuencia de cada elemento en un HashMap, digamos M .
- Inicialice dos variables, digamos maxValue como INT_MIN y minFreq como INT_MAX que almacenan el elemento máximo resultante y almacenan la frecuencia mínima entre todas las frecuencias.
- Iterar sobre el mapa M y realizar los siguientes pasos:
- Si la frecuencia del elemento actual es menor que minFreq , actualice el valor de minFreq a la frecuencia actual y el valor de maxValue al elemento actual.
- Si la frecuencia del elemento actual es igual a minFreq y el valor de maxValue es menor que el valor actual, actualice el valor de maxValue al elemento actual.
- Después de completar los pasos anteriores, imprima el valor de maxValue como el elemento resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum element
// with the minimum frequency
int maxElementWithMinFreq(int* arr, int N)
{
// Stores the frequency of array
// elements
unordered_map<int, int> mp;
// Find the frequency and store
// in the map
for (int i = 0; i < N; i++) {
mp[arr[i]]++;
}
// Initialize minFreq to the maximum
// value and minValue to the minimum
int minFreq = INT_MAX;
int maxValue = INT_MIN;
// Traverse the map mp
for (auto x : mp) {
int num = x.first;
int freq = x.second;
// If freq < minFreq, then update
// minFreq to freq and maxValue
// to the current element
if (freq < minFreq) {
minFreq = freq;
maxValue = num;
}
// If freq is equal to the minFreq
// and current element > maxValue
// then update maxValue to the
// current element
else if (freq == minFreq
&& maxValue < num) {
maxValue = num;
}
}
// Return the resultant maximum value
return maxValue;
}
// Driver Code
int main()
{
int arr[] = { 2, 2, 5, 50, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxElementWithMinFreq(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the maximum element
// with the minimum frequency
static int maxElementWithMinFreq(int[] arr, int N)
{
// Stores the frequency of array
// elements
HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>();
// Find the frequency and store
// in the map
for (int i = 0; i < N; i++) {
if(mp.containsKey(arr[i])){
mp.put(arr[i], mp.get(arr[i])+1);
}else{
mp.put(arr[i], 1);
}
}
// Initialize minFreq to the maximum
// value and minValue to the minimum
int minFreq = Integer.MAX_VALUE;
int maxValue = Integer.MIN_VALUE;
// Traverse the map mp
for (Map.Entry<Integer,Integer> x : mp.entrySet()){
int num = x.getKey();
int freq = x.getValue();
// If freq < minFreq, then update
// minFreq to freq and maxValue
// to the current element
if (freq < minFreq) {
minFreq = freq;
maxValue = num;
}
// If freq is equal to the minFreq
// and current element > maxValue
// then update maxValue to the
// current element
else if (freq == minFreq
&& maxValue < num) {
maxValue = num;
}
}
// Return the resultant maximum value
return maxValue;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 2, 5, 50, 1 };
int N = arr.length;
System.out.print(maxElementWithMinFreq(arr, N));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python 3 program for the above approach import sys from collections import defaultdict # Function to find the maximum element # with the minimum frequency def maxElementWithMinFreq(arr, N): # Stores the frequency of array # elements mp = defaultdict(int) # Find the frequency and store # in the map for i in range(N): mp[arr[i]] += 1 # Initialize minFreq to the maximum # value and minValue to the minimum minFreq = sys.maxsize maxValue = -sys.maxsize-1 # Traverse the map mp for x in mp: num = x freq = mp[x] # If freq < minFreq, then update # minFreq to freq and maxValue # to the current element if (freq < minFreq): minFreq = freq maxValue = num # If freq is equal to the minFreq # and current element > maxValue # then update maxValue to the # current element elif (freq == minFreq and maxValue < num): maxValue = num # Return the resultant maximum value return maxValue # Driver Code if __name__ == "__main__": arr = [2, 2, 5, 50, 1] N = len(arr) print(maxElementWithMinFreq(arr, N)) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the maximum element
// with the minimum frequency
static int maxElementWithMinFreq(int []arr, int N)
{
// Stores the frequency of array
// elements
Dictionary<int, int> mp = new Dictionary<int,int>();
// Find the frequency and store
// in the map
for (int i = 0; i < N; i++) {
if(mp.ContainsKey(arr[i]))
mp[arr[i]]++;
else
mp.Add(arr[i],1);
}
// Initialize minFreq to the maximum
// value and minValue to the minimum
int minFreq = Int32.MaxValue;
int maxValue = Int32.MinValue;
// Traverse the map mp
foreach(KeyValuePair<int,int> x in mp) {
int num = x.Key;
int freq = x.Value;
// If freq < minFreq, then update
// minFreq to freq and maxValue
// to the current element
if (freq < minFreq) {
minFreq = freq;
maxValue = num;
}
// If freq is equal to the minFreq
// and current element > maxValue
// then update maxValue to the
// current element
else if (freq == minFreq
&& maxValue < num) {
maxValue = num;
}
}
// Return the resultant maximum value
return maxValue;
}
// Driver Code
public static void Main()
{
int []arr = { 2, 2, 5, 50, 1 };
int N = arr.Length;
Console.Write(maxElementWithMinFreq(arr, N));
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the maximum element
// with the minimum frequency
function maxElementWithMinFreq(arr, N) {
// Stores the frequency of array
// elements
let mp = new Map();
// Find the frequency and store
// in the map
for (let i = 0; i < N; i++) {
if (mp.has(arr[i])) {
mp.set(arr[i], mp.get(arr[i]) + 1);
}
else {
mp.set(arr[i], 1);
}
}
// Initialize minFreq to the maximum
// value and minValue to the minimum
let minFreq = Number.MAX_VALUE
let maxValue = Number.MIN_VALUE;
// Traverse the map mp
for (let [key, value] of mp) {
let num = key;
let freq = value;
// If freq < minFreq, then update
// minFreq to freq and maxValue
// to the current element
if (freq < minFreq) {
minFreq = freq;
maxValue = num;
}
// If freq is equal to the minFreq
// and current element > maxValue
// then update maxValue to the
// current element
else if (freq == minFreq
&& maxValue < num) {
maxValue = num;
}
}
// Return the resultant maximum value
return maxValue;
}
// Driver Code
let arr = [2, 2, 5, 50, 1];
let N = arr.length;
document.write(maxElementWithMinFreq(arr, N));
// This code is contributed by Potta Lokesh
</script>
Producción:
50
Complejidad temporal: O(N)
Espacio auxiliar: O(N)